Tree Traversal Postorder Left Right Root in DSA Javascript

Mental Model

Visit the left side first, then the right side, and finally the root node last.

Analogy: Imagine cleaning a room by first tidying the left corner, then the right corner, and only after both are clean, you clean the center of the room.

    1
   / \
  2   3
 / \
4   5
↑ root

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 2 has children 4 (left) and 5 (right)

Goal: Print nodes in postorder: left subtree, right subtree, then root

Step 1: Traverse left subtree of root (1), move to node 2

    1
   / \
  [2] 3
 / \
4   5
↑ current at 2

Why: We must visit left subtree before root

Step 2: Traverse left subtree of node 2, move to node 4

    1
   / \
  2   3
 / \
[4]  5
↑ current at 4

Why: Left subtree of 2 must be visited first

Step 3: Node 4 has no children, print 4 and return to node 2

4 printed
    1
   / \
  2   3
 / \
4   5
↑ back at 2

Why: Leaf node visited, now visit right subtree

Step 4: Traverse right subtree of node 2, move to node 5

    1
   / \
  2   3
 / \
4  [5]
↑ current at 5

Why: Right subtree of 2 must be visited after left

Step 5: Node 5 has no children, print 5 and return to node 2

5 printed
    1
   / \
  2   3
 / \
4   5
↑ back at 2

Why: Leaf node visited, now print node 2

Step 6: Print node 2 and return to root 1

2 printed
    1
   / \
  2   3
 / \
4   5
↑ back at 1

Why: Both subtrees of 2 visited, now print 2

Step 7: Traverse right subtree of root (1), move to node 3

    1
   / \
  2  [3]
 / \
4   5
↑ current at 3

Why: Right subtree of root must be visited after left

Step 8: Node 3 has no children, print 3 and return to root 1

3 printed
    1
   / \
  2   3
 / \
4   5
↑ back at 1

Why: Leaf node visited, now print root

Step 9: Print root node 1

1 printed
    1
   / \
  2   3
 / \
4   5
Traversal complete

Why: All subtrees visited, print root last

Result:

4 -> 5 -> 2 -> 3 -> 1 -> null

Annotated Code

DSA Javascript

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function postorderTraversal(root) {
  const result = [];
  function traverse(node) {
    if (node === null) return;
    traverse(node.left); // visit left subtree
    traverse(node.right); // visit right subtree
    result.push(node.val); // visit root last
  }
  traverse(root);
  return result;
}

// Build tree from dry_run input
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);

const output = postorderTraversal(root);
console.log(output.join(' -> ') + ' -> null');

if (node === null) return;

stop traversal when no node to visit

traverse(node.left); // visit left subtree

advance to left child first

traverse(node.right); // visit right subtree

then advance to right child

result.push(node.val); // visit root last

add current node value after children visited

Output

4 -> 5 -> 2 -> 3 -> 1 -> null

Complexity Analysis

Time: O(n) because each node is visited exactly once

Space: O(n) due to recursion stack and result storage for all nodes

vs Alternative: Compared to iterative traversal, recursive is simpler but uses call stack; iterative may use explicit stack but same O(n) time

Edge Cases

Empty tree (root is null)

Returns empty list without error

DSA Javascript

if (node === null) return;

Single node tree

Returns list with single node value

DSA Javascript

if (node === null) return;

Tree with only left children

Visits all left nodes before root

DSA Javascript

traverse(node.left);

When to Use This Pattern

When you need to process children before the parent, especially for deleting or evaluating expressions, use postorder traversal because it ensures children are handled first.

Common Mistakes

Mistake: Visiting root before children (preorder) instead of after
Fix: Move the root visit (push) after traversing left and right children

Mistake: Forgetting to check for null node before recursion
Fix: Add base case 'if (node === null) return;' to stop recursion

Summary

Visits left subtree, then right subtree, then the root node last.

Use when you want to process children before their parent, like in expression evaluation or tree deletion.

The key is to delay visiting the root until both subtrees are fully processed.

Practice

1. What is the order of nodes visited in a postorder tree traversal?

easy

A. Left subtree, Right subtree, Root node

B. Root node, Left subtree, Right subtree

C. Root node, Right subtree, Left subtree

D. Right subtree, Left subtree, Root node

Solution

1. Step 1: Understand postorder traversal definition

   Postorder traversal visits the left subtree first, then the right subtree, and finally the root node.

2. Step 2: Match the order with options

   Left subtree, Right subtree, Root node matches the order Left, Right, Root exactly.

3. Final Answer:

   Left subtree, Right subtree, Root node -> Option A

4. Quick Check:

   Postorder = Left, Right, Root [OK]

Hint: Remember: postorder ends with root node [OK]

Common Mistakes:

• Confusing postorder with preorder or inorder
• Visiting root node first instead of last
• Swapping left and right subtree order

2. Which of the following is the correct syntax to perform a postorder traversal function call in JavaScript assuming postorder(node) is defined?

easy

A. console.log(node.value); postorder(node.left); postorder(node.right);

B. console.log(node.value); postorder(node.right); postorder(node.left);

C. postorder(node.right); postorder(node.left); console.log(node.value);

D. postorder(node.left); postorder(node.right); console.log(node.value);

Solution

1. Step 1: Recall postorder traversal steps

   Postorder visits left subtree, then right subtree, then root node.

2. Step 2: Check syntax order

   postorder(node.left); postorder(node.right); console.log(node.value); calls postorder on left, then right, then prints root value last, matching postorder.

3. Final Answer:

   postorder(node.left); postorder(node.right); console.log(node.value); -> Option D

4. Quick Check:

   Left, Right, Root call order = postorder(node.left); postorder(node.right); console.log(node.value); [OK]

Hint: Print root after left and right calls [OK]

Common Mistakes:

• Printing root before recursive calls
• Swapping left and right recursive calls
• Missing recursive calls for subtrees

3. Given the binary tree below, what is the output of a postorder traversal?

    1
   / \
  2   3
 / \
4   5

medium

A. [1, 2, 3, 4, 5]

B. [4, 5, 2, 3, 1]

C. [2, 4, 5, 3, 1]

D. [4, 2, 5, 3, 1]

Solution

1. Step 1: Traverse left subtree of root (1)

   Left subtree rooted at 2: postorder is left(4), right(5), root(2) -> [4, 5, 2]

2. Step 2: Traverse right subtree and root

   Right subtree is node 3 -> [3]. Then root 1 last -> [1]. Combine: [4, 5, 2] + [3] + [1] = [4, 5, 2, 3, 1]

3. Final Answer:

   [4, 5, 2, 3, 1] -> Option B

4. Quick Check:

   Postorder = Left, Right, Root = [4,5,2,3,1] [OK]

Hint: Visit left subtree fully before right, then root [OK]

Common Mistakes:

• Listing root before subtrees
• Mixing up left and right subtree order
• Confusing preorder or inorder output

4. The following JavaScript code attempts a postorder traversal but produces incorrect output. What is the error?

function postorder(node) {
  if (!node) return;
  console.log(node.value);
  postorder(node.left);
  postorder(node.right);
}

medium

A. The left subtree is visited after the right subtree

B. The function does not check if node is null

C. The root node is printed before its children, not after

D. The function is missing a return statement

Solution

1. Step 1: Analyze print order in code

   The code prints node.value before recursive calls, so root prints first.

2. Step 2: Compare with postorder definition

   Postorder requires printing root after left and right subtrees, so printing first is wrong.

3. Final Answer:

   The root node is printed before its children, not after -> Option C

4. Quick Check:

   Postorder prints root last, code prints root first [OK]

Hint: Print root after recursive calls for postorder [OK]

Common Mistakes:

• Printing root before recursive calls
• Ignoring base case for null nodes
• Swapping left and right subtree calls

5. You want to collect all node values of a binary tree in postorder traversal into an array. Which code snippet correctly does this in JavaScript?

hard

A. function postorder(node, arr = []) {
if (!node) return arr;
postorder(node.left, arr);
postorder(node.right, arr);
arr.push(node.value);
return arr;
}

B. function postorder(node, arr = []) {
if (!node) return arr;
arr.push(node.value);
postorder(node.left, arr);
postorder(node.right, arr);
return arr;
}

C. function postorder(node, arr = []) {
if (!node) return arr;
postorder(node.right, arr);
postorder(node.left, arr);
arr.push(node.value);
return arr;
}

D. function postorder(node, arr = []) {
if (!node) return arr;
postorder(node.left, arr);
arr.push(node.value);
postorder(node.right, arr);
return arr;
}

Solution

1. Step 1: Check traversal order in each snippet

   function postorder(node, arr = []) { if (!node) return arr; postorder(node.left, arr); postorder(node.right, arr); arr.push(node.value); return arr; } visits left subtree, then right subtree, then pushes root value last, matching postorder.

2. Step 2: Verify array accumulation and return

   function postorder(node, arr = []) { if (!node) return arr; postorder(node.left, arr); postorder(node.right, arr); arr.push(node.value); return arr; } correctly passes and returns the array, accumulating values in postorder.

3. Final Answer:

   Option A code snippet -> Option A

4. Quick Check:

   Left, Right, Root with arr.push last = function postorder(node, arr = []) { if (!node) return arr; postorder(node.left, arr); postorder(node.right, arr); arr.push(node.value); return arr; } [OK]

Hint: Push root value after left and right recursive calls [OK]

Common Mistakes:

• Pushing root value before recursive calls
• Swapping left and right subtree calls
• Not returning the array properly