Getting Started with Trees: Traversal Methods

Welcome back, fellow coding enthusiasts!

This is the second part of a sequel to the guide on trees. If you missed the first part which is about the depth and height of trees, you can check it out here.

This blog will go through the different traversal methods for trees.

Knowing tree traversal methods is crucial because they help developers efficiently visit every node in a tree. These methods are used in real-life situations like:

• Printing the contents of a directory hierarchy
• Evaluating mathematical expressions represented as a tree
• Retrieving values from a binary search tree

So, let’s dive right in and explore!

What does traversal mean?

Traversal refers to visiting or passing through all the nodes in a data structure such as a tree or a graph. It’s a way to iterate over all the elements and visit each node, usually to find a specific component, perform some operation on the nodes, or create a new representation of the data structure.

There are three main basic traversal methods for trees:

1. Pre-order traversal: In pre-order traversal, the root node is visited first, then its left and right sub-trees are visited.
2. In-order traversal: In in-order traversal, the left sub-tree is visited first, then the root node, and finally the right sub-tree.
3. Post-order traversal: In post-order traversal, the left and right sub-trees are visited first, and then the root node is visited last.

Each traversal method has its use case, and the choice of method depends on the task.

Pre-order Traversal

The correct order in pre-order traversal is as follows:

• Visit the root node.
• Traverse the left subtree (if exists).
• Traverse the right subtree (if exists).

The order of pre-order traversal (visiting the node, left subtree, and right subtree) is not just arbitrary, but it has specific applications. For example, pre-order is often used to create a copy of a binary tree, where each node’s value is written to a new node before its left and right subtrees are processed. Another application is to evaluate expressions represented by binary trees, where the operator is processed before its operands.

Here is an example of the output that we should get after the pre-order traversal of a tree:

There are two standard methods that we can use to perform a pre-order traversal.

LeetCode — 144. Binary Tree Preorder Traversal

Recursive Method

This method involves visiting the root node first, then recursively visiting the left and right subtrees. Here is how we can implement it:

var preorderTraversal = function(root) {
    
    if(!root) return []
    
    const left = preorderTraversal(root.left)
    const right = preorderTraversal(root.right)
    
    return [ root.val, ...left, ...right]
    
};

This recursively calls itself for the left and right children of the node (if they exist) and the recursion will end when we reach a leaf node. Then it returns the order specified for pre-order traversal.

Iterative Method

This method involves using a stack to store nodes as they are being visited. The algorithm starts by pushing the root node onto the stack and then repeating the following steps until the stack is empty:

• Pop a node from the stack
• Push its node value to the resulting array
• Push its right and left children onto the stack (if they exist).

Here is how we can implement it:

var preorderTraversal = function(root) {
  if (!root) return [];
  const stack = [root];
  const result = [];
  while (stack.length) {
    const node = stack.pop();
    result.push(node.val);
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  return result;
};

In-order Traversal

The correct order in in-order traversal is as follows:

• Visit the left subtree (if it exists)
• Visit the current node
• Visit the right subtree (if it exists)

The primary purpose of in-order traversal is to visit all the nodes of a tree in sorted order.

Here is an example of the in-order traversal of a tree:

94. Binary Tree Inorder Traversal

Recursive Method

This will be very similar to the function that we have for recursive pre-order because all we have to do is to change the order of the subtrees and root values.

function inorderTraversal(root) {
    
    if(!root) return []
    
    const left = inorderTraversal(root.left)
    const right = inorderTraversal(root.right)
    
    return [...left, root.val, ...right]
      
}

The left subtree goes first, the root value follows and then the right subtree comes.

Iterative Method

function inorderTraversal(root) {
  let stack = [];
  let result = [];
  let current = root;

  while (current || stack.length) {
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    result.push(current.val);
    current = current.right;
  }
  return result;
}

An iterative in-order traversal uses a stack to keep track of nodes and a variable node to keep track of the current node.

The algorithm pushes the current node to the stack, moves to its left child, and adds its value to the result array when there is no more left child. Then after adding the current value to the result, the new current becomes the right child of the current. The process continues until the stack is empty, then the result array is returned.

Post-order Traversal

The correct order in post-order traversal is as follows:

• Visit the left subtree (if it exists)
• Visit the right subtree (if it exists)
• Visit the current node

Post-order traversal is useful in situations where we need to perform an operation on a tree that depends on the values of its child nodes before the value of the parent node can be computed.

Here is an example of the post-order traversal of a tree:

145. Binary Tree Postorder Traversal

Recursive Method

If you think the recursion code for post-order traversal will be quite similar to the others, you are absolutely correct! Here is how:

var postorderTraversal = function(root) {
    
    if(!root) return []
    
    const left = postorderTraversal(root.left)
    const right = postorderTraversal(root.right)
    
    return [...left, ...right, root.val]
      
};

As you can see, only the order of the subtrees and values changed.

Iterative Method

We will use a stack and result array for post-order traversal.

The “current” variable will keep track of the node being processed. The algorithm will push the current node to the stack and move to its right child. When there are no more right children, the top node in the stack will be popped and its value added to the beginning of the result.

The current variable will be updated to the left child of the popped node. This will continue until the stack is empty.

function postorderTraversal(root) {
 let stack = [];
 let result = [];
 let current = root;

 while (current || stack.length) {
   while (current) {
     stack.push(current);
     result.unshift(current.val);
     current = current.right;
   }
   current = stack.pop();
   current = current.left;
 }
 return result;
}

Comparison Between Two Methods for All Traverses

Benefits:

• The recursive method is easy to implement and understand, making it a good choice for beginners.
• The iterative method is easier to debug as an algorithm, as each step can be traced and monitored.

Time Complexity:

• The recursive and iterative methods both have a time complexity of O(n), where n is the number of nodes in the tree.

Space Complexity:

• The recursive method has a space complexity of O(n) due to the call stack, which can be as large as the number of nodes in the worst case.
• The iterative method has a space complexity of O(h), where h is the height of the tree. This is because the size of the stack is proportional to the height of the tree.

Conclusion

Tree traversing methods are important techniques for processing data stored in trees. The three main types of tree traversals are pre-order, in-order, and post-order. Each method has its own advantages and usage cases.

Pre-order traversal visits the root node first, then its left and right children. In-order traversal visits the left child, then the root node, and finally the right child. Post-order traversal visits the left child, then the right child, and finally the root node.

Both iterative and recursive implementations are possible for each of these methods, each with its own time and space complexities. In conclusion, tree traversal methods provide a flexible and efficient way to process tree data and are widely used in many areas of computer science.