Your Progress

20/30 completed

67% complete. Continue learning to master DSA!

Tree Traversal Algorithms

Tree traversal is the process of visiting each node in a tree data structure exactly once. Different traversal methods can visit nodes in different orders, each suited for specific applications.

Key Takeaways

Depth-First Traversals include pre-order (root-left-right), in-order (left-root-right), and post-order (left-right-root)
Breadth-First Traversal visits nodes level-by-level, from left to right
Tree traversals can be implemented recursively or iteratively
In-order traversal of a binary search tree yields nodes in sorted order
Time complexity for all traversal methods is O(n) where n is the number of nodes

Understanding Tree Traversal

Tree traversal is a fundamental operation in tree data structures that involves systematically visiting every node in the tree. Unlike linear data structures like arrays or linked lists that have a natural sequential order, trees can be traversed in multiple ways.

Tree Traversal Categories

Depth-First Traversal (DFT)

Explores as far as possible along each branch before backtracking.

Pre-order (Root, Left, Right)
In-order (Left, Root, Right)
Post-order (Left, Right, Root)

Breadth-First Traversal (BFT)

Explores all nodes at the present depth before moving to nodes at the next depth level.

Level-order traversal

Example Binary Tree

We'll use this binary tree for our traversal examples:

This binary tree has 7 nodes with node 1 as the root. We'll demonstrate different traversal methods on this tree.

Depth-First Traversal Methods

1. Pre-order Traversal (Root-Left-Right)

In pre-order traversal, we visit the root node first, then traverse the left subtree, and finally the right subtree.

Order for our example tree:

1 → 2 → 4 → 5 → 3 → 6 → 7

Recursive Implementation:

function preOrderTraversal(root) {
  if (root === null) return;
  
  // Visit the root node
  console.log(root.value);
  
  // Traverse left subtree
  preOrderTraversal(root.left);
  
  // Traverse right subtree
  preOrderTraversal(root.right);
}

// Example usage
preOrderTraversal(rootNode); // Outputs: 1, 2, 4, 5, 3, 6, 7

Iterative Implementation:

function preOrderIterative(root) {
  if (root === null) return;
  
  const stack = [root];
  
  while (stack.length > 0) {
    // Pop a node from the stack
    const node = stack.pop();
    
    // Print the node's value
    console.log(node.value);
    
    // Push right child first so that left child is processed first
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
}

// Example usage
preOrderIterative(rootNode); // Outputs: 1, 2, 4, 5, 3, 6, 7

Applications:

Creating a copy of the tree
Getting prefix expression of an expression tree
Serializing and deserializing a binary tree

2. In-order Traversal (Left-Root-Right)

In in-order traversal, we first traverse the left subtree, then visit the root node, and finally traverse the right subtree.

Order for our example tree:

4 → 2 → 5 → 1 → 6 → 3 → 7

Recursive Implementation:

function inOrderTraversal(root) {
  if (root === null) return;
  
  // Traverse left subtree
  inOrderTraversal(root.left);
  
  // Visit the root node
  console.log(root.value);
  
  // Traverse right subtree
  inOrderTraversal(root.right);
}

// Example usage
inOrderTraversal(rootNode); // Outputs: 4, 2, 5, 1, 6, 3, 7

Iterative Implementation:

function inOrderIterative(root) {
  if (root === null) return;
  
  const stack = [];
  let current = root;
  
  while (current !== null || stack.length > 0) {
    // Reach the leftmost node
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }
    
    // Current is now null, pop an element from the stack
    current = stack.pop();
    
    // Visit the node
    console.log(current.value);
    
    // Move to the right subtree
    current = current.right;
  }
}

// Example usage
inOrderIterative(rootNode); // Outputs: 4, 2, 5, 1, 6, 3, 7

Applications:

Getting values in sorted order in a binary search tree
Getting infix expression from an expression tree

3. Post-order Traversal (Left-Right-Root)

In post-order traversal, we first traverse the left subtree, then the right subtree, and finally visit the root node.

Order for our example tree:

4 → 5 → 2 → 6 → 7 → 3 → 1

Recursive Implementation:

function postOrderTraversal(root) {
  if (root === null) return;
  
  // Traverse left subtree
  postOrderTraversal(root.left);
  
  // Traverse right subtree
  postOrderTraversal(root.right);
  
  // Visit the root node
  console.log(root.value);
}

// Example usage
postOrderTraversal(rootNode); // Outputs: 4, 5, 2, 6, 7, 3, 1

Iterative Implementation:

function postOrderIterative(root) {
  if (root === null) return;
  
  const stack1 = [root];
  const stack2 = [];
  
  // First stack is to help us build the second stack
  while (stack1.length > 0) {
    const node = stack1.pop();
    stack2.push(node);
    
    if (node.left) stack1.push(node.left);
    if (node.right) stack1.push(node.right);
  }
  
  // Second stack now has nodes in post-order
  while (stack2.length > 0) {
    const node = stack2.pop();
    console.log(node.value);
  }
}

// Example usage
postOrderIterative(rootNode); // Outputs: 4, 5, 2, 6, 7, 3, 1

Applications:

Deleting the tree (nodes must be deleted bottom-up)
Getting postfix expression of an expression tree
Finding the height of a tree

Breadth-First Traversal: Level Order

Level order traversal visits nodes level by level, from left to right. It uses a queue data structure instead of recursion or a stack.

Level Order Traversal

Order for our example tree:

1 → 2 → 3 → 4 → 5 → 6 → 7

Implementation:

function levelOrderTraversal(root) {
  if (root === null) return;
  
  const queue = [root];
  
  while (queue.length > 0) {
    // Remove the front of the queue
    const node = queue.shift();
    
    // Visit the node
    console.log(node.value);
    
    // Add the node's children to the queue
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
}

// Example usage
levelOrderTraversal(rootNode); // Outputs: 1, 2, 3, 4, 5, 6, 7

Printing Levels Separately:

function printLevelOrder(root) {
  if (root === null) return;
  
  const queue = [root];
  
  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];
    
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      currentLevel.push(node.value);
      
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    
    console.log(currentLevel.join(' '));
  }
}

// Example usage
printLevelOrder(rootNode);
// Outputs:
// 1
// 2 3
// 4 5 6 7

Applications:

Level-by-level processing
Finding the minimum depth of a binary tree
Connect nodes at the same level in a binary tree
Zigzag traversal of a binary tree

Time and Space Complexity

Traversal Method	Time Complexity	Space Complexity
Pre-order (Recursive)	O(n)	O(h) - height of tree
Pre-order (Iterative)	O(n)	O(h) - height of tree
In-order (Recursive)	O(n)	O(h) - height of tree
In-order (Iterative)	O(n)	O(h) - height of tree
Post-order (Recursive)	O(n)	O(h) - height of tree
Post-order (Iterative)	O(n)	O(n) - worst case
Level Order	O(n)	O(w) - max width of tree

In the worst case, the space complexity for recursive implementations is O(n) for a skewed tree (where h = n). Similarly, for level order traversal, the space complexity could be O(n) for a complete binary tree in the last level.

Advanced Tree Traversal Techniques

Morris Traversal

A way to traverse binary trees using O(1) space by temporarily modifying the tree structure.

Key Benefits:

No recursion or stack required
O(1) space complexity
Useful when stack space is limited

Zigzag Traversal

A modified level order traversal where levels are processed in alternating directions.

Example Output:

For our example tree:
Level 0: 1
Level 1: 3, 2 (right to left)
Level 2: 4, 5, 6, 7 (left to right)

Boundary Traversal

Visits all the boundary nodes of a binary tree in counter-clockwise direction.

Process:

Print left boundary (top-down)
Print leaves (left to right)
Print right boundary (bottom-up)

Diagonal Traversal

Visits nodes that are on the same diagonal line from top to bottom.

Implementation Hint:

Use a queue or a hash map to group nodes by their diagonal distance.

Common Tree Traversal Problems

1. Construct a Binary Tree from Traversals

A binary tree can be constructed from certain combinations of traversals:

From In-order and Pre-order traversals
From In-order and Post-order traversals
Cannot be constructed from just Pre-order and Post-order (without additional info)

2. Tree Serialization and Deserialization

Convert a tree to a string (serialization) and back (deserialization) using traversal techniques.

3. Check if Two Trees are Identical

function areIdentical(root1, root2) {
  // Both empty
  if (root1 === null && root2 === null) return true;
  
  // Both non-empty, compare them
  if (root1 !== null && root2 !== null) {
    return (
      root1.value === root2.value &&
      areIdentical(root1.left, root2.left) &&
      areIdentical(root1.right, root2.right)
    );
  }
  
  // One empty, one not
  return false;
}

4. Finding the Diameter of a Binary Tree

The diameter (or width) of a tree is the number of nodes on the longest path between any two leaf nodes.

Conclusion

Tree traversal algorithms are fundamental to many tree-based operations and problem-solving techniques. Understanding the different traversal methods and when to apply them is essential for efficient manipulation of tree data structures. Whether you're dealing with binary search trees, expression trees, or other specialized tree structures, choosing the right traversal method can significantly impact the elegance and efficiency of your solution.

Remember

When choosing a traversal method, consider:

The order in which you need to process nodes
The specific requirements of your problem
Whether recursive or iterative implementation is more appropriate
The space constraints of your application

Next Steps

To further your understanding of trees and related algorithms, explore these topics:

Binary Search Trees

Learn about a specialized tree with ordered nodes

Depth-First Search

Apply traversal concepts to graph structures

Breadth-First Search

Expand your knowledge of level-order algorithms

Your Progress

Key Takeaways

Understanding Tree Traversal

Tree Traversal Categories

Depth-First Traversal (DFT)

Breadth-First Traversal (BFT)

Example Binary Tree

Depth-First Traversal Methods

1. Pre-order Traversal (Root-Left-Right)

Order for our example tree:

Recursive Implementation:

Iterative Implementation:

Applications:

2. In-order Traversal (Left-Root-Right)

Order for our example tree:

Recursive Implementation:

Iterative Implementation:

Applications:

3. Post-order Traversal (Left-Right-Root)

Order for our example tree:

Recursive Implementation:

Iterative Implementation:

Applications:

Breadth-First Traversal: Level Order

Level Order Traversal

Order for our example tree:

Implementation:

Printing Levels Separately:

Applications:

Time and Space Complexity

Advanced Tree Traversal Techniques

Morris Traversal

Zigzag Traversal

Boundary Traversal

Diagonal Traversal

Common Tree Traversal Problems

1. Construct a Binary Tree from Traversals

2. Tree Serialization and Deserialization

3. Check if Two Trees are Identical

4. Finding the Diameter of a Binary Tree

Conclusion

Remember

Next Steps

Binary Search Trees

Depth-First Search

Breadth-First Search

Related Tutorials

Related Tutorials

Binary Search Trees

Depth-First Search

Breadth-First Search