Tree Traversal Postorder Left Right Root in DSA Javascript - Execution Trace

Concept Flow - Tree Traversal Postorder Left Right Root

Start at root node

↓

Traverse left subtree

↓

Traverse right subtree

↓

Visit current node (root)

↓

Back to parent node

↓

Repeat until all nodes visited

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

Execution Sample

DSA Javascript

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

This code prints nodes of a binary tree in postorder: left, right, then root.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Tree State (Visual)
1	Start at root	A	current = A	A / \ B C
2	Traverse left subtree	B	current = B	A / \ B C
3	Traverse left subtree of B	D	current = D	A / \ B C / D
4	Visit D (leaf)	D	print D	A / \ B C / D
5	Traverse right subtree of B	E	current = E	A / \ B C / \ D E
6	Visit E (leaf)	E	print E	A / \ B C / \ D E
7	Visit B (after children)	B	print B	A / \ B C / \ D E
8	Traverse right subtree	C	current = C	A / \ B C / \ D E F
9	Traverse left subtree of C	F	current = F	A / \ B C / \ D E F
10	Visit F (leaf)	F	print F	A / \ B C / \ D E F
11	Traverse right subtree of C	G	current = G	A / \ B C / \ D E F \ G
12	Visit G (leaf)	G	print G	A / \ B C / \ D E F \ G
13	Visit C (after children)	C	print C	A / \ B C / \ D E F \ G
14	Visit A (root after children)	A	print A	A / \ B C / \ D E F \ G
15	Traversal complete	None	None	All nodes visited in postorder: D E B F G C A

💡 All nodes visited in postorder; recursion ends when node is null.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11	After Step 12	After Step 13	After Step 14	Final
current	root (A)	A	B	D	D	E	E	B	C	F	F	G	G	C	A	None
printed_nodes	[]	[]	[]	[]	[D]	[D]	[D, E]	[D, E, B]	[D, E, B]	[D, E, B]	[D, E, B, F]	[D, E, B, F]	[D, E, B, F, G]	[D, E, B, F, G, C]	[D, E, B, F, G, C, A]	[D, E, B, F, G, C, A]

Key Moments - 3 Insights

Why do we print the node value after traversing left and right children?

Because postorder means visiting left subtree, then right subtree, and only then the root node. This is shown in execution_table rows 4, 6, 7, 10, 12, 13, and 14 where printing happens after children are visited.

What happens when a node has no children?

The function prints the node immediately since left and right recursive calls return immediately (null). This is shown in steps 4, 6, 10, and 12 where leaf nodes D, E, F, G are printed.

How does the traversal know when to stop?

When the node is null, the function returns without action. This base case stops recursion and is the reason traversal ends after all nodes are visited, as noted in exit_note.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, which nodes have been printed so far?

A [D, E, B, F]

B [D, E]

C [D, E, B]

D [D, E, B, F, G]

💡 Hint

Check the 'printed_nodes' variable in variable_tracker after step 7.

At which step does the traversal visit the root node 'A'?

A Step 13

B Step 14

C Step 15

D Step 12

💡 Hint

Look at the 'Node Visited' and 'Operation' columns in execution_table.

If node 'C' had no right child, how would the printed order change?

A G would be missing, printed order ends with F C A

B No change, G is printed anyway

C Traversal would stop early at C

D Node C would be printed before F

💡 Hint

Refer to the traversal order in execution_table and consider missing right subtree of C.

Concept Snapshot

Postorder traversal visits nodes in Left → Right → Root order.
Use recursion: traverse left subtree, then right subtree, then visit node.
Print or process node only after children.
Base case: if node is null, return immediately.
Common for tree algorithms needing bottom-up processing.

Full Transcript

Postorder traversal means visiting the left subtree first, then the right subtree, and finally the root node. The code uses recursion to do this. It starts at the root, goes left until it hits a leaf, prints that leaf, then goes right, prints that leaf, and finally prints the parent node. This repeats up the tree until all nodes are printed. The base case is when the node is null, which stops recursion. The printed order for the example tree is D, E, B, F, G, C, A.

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