General

No Comments

Pre-order Traversal in a Binary Tree

Pre-order traversal is one of the fundamental methods for traversing a binary tree. In this traversal method, the nodes are recursively visited in this order:

  1. Visit the root node.
  2. Traverse the left subtree in Pre-Order.
  3. Traverse the right subtree in Pre-Order.

Pre-order traversal is particularly useful when you want to create a copy of a tree or need to prefix the expression of a binary tree.

Problem Statement

Given the root of a binary tree, return the pre-order traversal of its nodes’ values.

Example

Input:

    1
   / \
  2   3
 / \
4   5

Output:

[1, 2, 4, 5, 3]

Approach

We will look at two approaches to implementing Pre-Order Traversal:

  1. Recursive Approach
  2. Iterative Approach using a Stack

Recursive Approach

The recursive approach is straightforward and elegant. We follow the pre-order traversal steps by recursively visiting the root, left subtree, and right subtree.

Steps

  1. Initialize an empty array to store the traversal result.
  2. Define a recursive function that takes a node as input.
  3. If the node is null, return.
  4. Add the value of the node to the result array.
  5. Recursively call the function for the left child.
  6. Recursively call the function for the right child.
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const preOrderTraversal = (root) => {
  const result = [];
  const traverse = (node) => {
    if (!node) return;
    result.push(node.val);
    traverse(node.left);
    traverse(node.right);
  };
  traverse(root);
  return result;
};

// Test the function
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

console.log(preOrderTraversal(root)); // Output: [1, 2, 4, 5, 3]

Iterative Approach using a Stack

The iterative approach uses a stack to mimic the call stack used in recursion. This method is useful for understanding how traversal can be achieved without recursion.

Steps

  1. Initialize an empty stack and push the root node onto it.
  2. Initialize an empty array to store the traversal result.
  3. While the stack is not empty:
    • Pop a node from the stack.
    • Add the value of the node to the result array.
    • Push the right child of the node onto the stack (if it exists).
    • Push the left child of the node onto the stack (if it exists).
const preOrderTraversalIterative = (root) => {
  if (!root) return [];
  
  const stack = [root];
  const result = [];

  while (stack.length > 0) {
    const currentNode = stack.pop();
    result.push(currentNode.val);

    if (currentNode.right) {
      stack.push(currentNode.right);
    }
    if (currentNode.left) {
      stack.push(currentNode.left);
    }
  }

  return result;
};

// Test the function
console.log(preOrderTraversalIterative(root));//Output: [1, 2, 4, 5, 3]

Explanation

  1. TreeNode Class: A simple class to create tree nodes with properties for value (val), left child (left), and the right child (right).
  2. preOrderTraversal Function:
    • Initialize an empty array result to store the traversal result.
    • Define a recursive function traverse that processes each node.
    • If the node is null, return.
    • Add the value of the node to result.
    • Recursively traverse the left subtree and then the right subtree.
    • Return the result.
  3. preOrderTraversalIterative Function:
    • Initialize an empty stack and push the root node onto it.
    • Initialize an empty array result to store the traversal result.
    • While the stack is not empty, pop a node from the stack, add its value to result, and push its right and left children onto the stack (if they exist).
    • Return the result.

Close Menu