Tree Traversal

Table of contents

1. Binary Tree Node
2. Depth-First Traversal
   1. Recursion or Stack
   2. Recursive DFT
   3. Iterative DFT
      1. Pre and Inorder
      2. Postorder
3. Breadth-First Traversal

---

Binary Tree Node

Assume our tree is implemented as such:

template<typename T>
class BinaryTreeNode {
 public:
  using Node = BinaryTreeNode<T>;
  using NodePtr = shared_ptr<BinaryTreeNode<T>>;
  T val_;
  NodePtr left_;
  NodePtr right_;
  BinaryTreeNode(T val) : val_(val), left_(nullptr), right_(nullptr) {}
};

Pretty basic setup.

For further simplicity, we’ll assume T = int.

---

Depth-First Traversal

There are three actions that should be taken at step:

• Traverse the left subtree
• Traverse the right subtree
• Visit the node

Depending on when we visit the node, we can have three different types of depth-first traversal:

• Pre-order traversal: Visit the node before traversing the subtrees
• In-order traversal: Visit the node in between traversing the subtrees
• Post-order traversal: Visit the node after traversing the subtrees

Recursion or Stack

Depth-first traversal is usually implemented using recursion. You could also implement it iteratively using a stack.

For each traversal, we’ll return the result of the traversal as a vector of node values.

Recursive DFT

Very simple to implement.

The difference between the three types of traversal really just boils down to where you put the push.

void PreOrder(const NodePtr& node, vector<int>& res) {
  if (!node) return;
  res.push_back(node->val_);  // Pre-order
  PreOrder(node->left_, result);
  // res.push_back(node->val_);  // In-order
  PreOrder(node->right_, result);
  // res.push_back(node->val_);  // Post-order
}

Iterative DFT

Pre and Inorder

Because recursion is basically a stack under the hood, you can implement DFT iteratively using a stack.

You’re gonna need two while loops:

• One loop to keep popping the stack (equivalent to returning from a recursive call)
• Another loop to keep going deeper to the left subtree

void PreOrder(const NodePtr& node, vector<int>& res) {
  stack<NodePtr> s;
  NodePtr curr = node;
  while (curr || !s.empty()) {
    while (curr) {
      res.push_back(curr->val_);  // Pre-order
      s.push(curr);
      curr = curr->left_;
    }
    curr = s.top();
    s.pop();
    // res.push_back(curr->val_);  // In-order
    curr = curr->right_;
  }
}

Postorder

Iterative postorder traversal is a bit more complicated/different.

Why? Because preorder and inorder visits a node (the core action of the recursion) before visiting all left and right subtrees.

On the other hand, postorder needs to wait until right subtree is processed. But if you see our iterative implementation above, if we push to the res vector after curr = curr->right_, our original curr node is lost.

There is a simple implementation using two stacks. The idea is to dump processed nodes from the first stack into the second stack.

Since stack is LIFO, popping from the second stack will give us the correct order.

There is also a way to do it with one stack.

void PostOrder(const NodePtr& node, vector<int>& res) {
  stack <NodePtr> s1, s2;

  if (!node) return;

  s1.push(node);
  NodePtr curr;

  while (!s1.empty()) {
    curr = s1.top();
    s1.pop();
    s2.push(curr);  // Dump processed nodes to s2

    if (curr->left_) s1.push(curr->left_);
    if (curr->right_) s1.push(curr->right_);
  }

  while (!s2.empty()) {
    res.push_back(s2.top()->val_);
    s2.pop();
  }
}

---

Breadth-First Traversal

Level-order traversal uses a queue. After processing yourself, add all children to the queue to be processed.

void BreadthFirstTraversal(const NodePtr& root, vector<int>& res) {
  if (!root) return;
  queue<NodePtr> q;
  q.push(root);

  while (!q.empty()) {
    NodePtr curr = q.front();
    q.pop();
    res.push_back(curr->val_);

    if (curr->left_) q.push(curr->left_);
    if (curr->right_) q.push(curr->right_);
  }
}