We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Tree: Postorder Traversal
  2. Discussions

Tree: Postorder Traversal

  • logan_r_smith0
     + 0 comments

    C++ with iteration and an explicit stack. We (shallow) copy each node onto the stack. As we descend down the left or right of each node, we set their pointers to nullptr on the current node, so that when we return to the current node we know we've already visited them. This dovetails nicely with the leaf case, where both left and right are already null.

        void postOrder(Node *root) {
		    if (!root) return;
        std::vector<Node> stack;
        
        // assuming the tree is balanced, this is enough capacity
        // to traverse a tree with about a million nodes
        const auto cap = 20;
        stack.reserve(cap);
        
        stack.push_back(root);
        while (!stack.empty()) {
            auto& top = stack.back();
            if (!top.left && !top.right) {
                std::cout << top.data << ' ';
                stack.pop_back();
            } else {
                const auto next = std::exchange(top.left ?: top.right, nullptr);
                stack.push_back(*next);
            }
        }
    }