Tree Traversal Postorder Left Right Root in DSA Typescript - 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 or end if root

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

Execution Sample

DSA Typescript

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

This code visits nodes in postorder: left child, right child, then the node itself.

Execution Table

Step	Operation	Node Visited	Action	Tree State (Visited Nodes)
1	Start at root	A	Traverse left subtree	[]
2	Traverse left subtree	B	Traverse left subtree	[]
3	Traverse left subtree	D	Traverse left subtree	[]
4	Traverse left subtree	null	Return (no node)	[]
5	Traverse right subtree	null	Return (no node)	[]
6	Visit node	D	Print D	[D]
7	Traverse right subtree	E	Traverse left subtree	[D]
8	Traverse left subtree	null	Return (no node)	[D]
9	Traverse right subtree	null	Return (no node)	[D]
10	Visit node	E	Print E	[D, E]
11	Visit node	B	Print B	[D, E, B]
12	Traverse right subtree	C	Traverse left subtree	[D, E, B]
13	Traverse left subtree	F	Traverse left subtree	[D, E, B]
14	Traverse left subtree	null	Return (no node)	[D, E, B]
15	Traverse right subtree	null	Return (no node)	[D, E, B]
16	Visit node	F	Print F	[D, E, B, F]
17	Traverse right subtree	G	Traverse left subtree	[D, E, B, F]
18	Traverse left subtree	null	Return (no node)	[D, E, B, F]
19	Traverse right subtree	null	Return (no node)	[D, E, B, F]
20	Visit node	G	Print G	[D, E, B, F, G]
21	Visit node	C	Print C	[D, E, B, F, G, C]
22	Visit node	A	Print A	[D, E, B, F, G, C, A]
23	End	null	Traversal complete	[D, E, B, F, G, C, A]

💡 Traversal ends after visiting root node A and printing all nodes in postorder.

Variable Tracker

Variable	Start	After Step 6	After Step 11	After Step 16	After Step 21	Final
Current Node	A	D	B	F	C	null
Visited Nodes	[]	[D]	[D, E, B]	[D, E, B, F]	[D, E, B, F, G, C]	[D, E, B, F, G, C, A]
Call Stack Depth	1	3	2	3	2	0

Key Moments - 3 Insights

Why do we visit the current node only after traversing left and right subtrees?

Because postorder means Left, Right, Root order. The execution_table rows 6, 11, 16, 20, 21, and 22 show the node is printed only after both subtrees are fully traversed.

What happens when a node has no left or right child?

The traversal returns immediately (rows 4, 5, 8, 9, 14, 15, 18, 19) without printing, ensuring leaf nodes are visited correctly.

How does the call stack depth change during traversal?

It increases when going deeper into left/right children and decreases after visiting nodes, as shown in variable_tracker under Call Stack Depth.

Visual Quiz - 3 Questions

Look at the execution_table, what nodes have been visited after step 11?

A [D, E]

B [D]

C [D, E, B]

D [D, E, B, F]

💡 Hint

Check the 'Tree State (Visited Nodes)' column at step 11 in execution_table.

At which step does the traversal visit node 'C'?

A Step 21

B Step 20

C Step 22

D Step 16

💡 Hint

Look for 'Visit node' operation with node 'C' in execution_table.

If node 'B' had no right child, how would the visited nodes list change after step 11?

A [D, B, E]

B [D, B]

C [D, E, B]

D [B]

💡 Hint

Without right child 'E', node 'B' visits only left child 'D' before itself, see execution_table pattern.

Concept Snapshot

Postorder traversal visits nodes in Left → Right → Root order.
Use recursion: traverse left subtree, then right subtree, then visit node.
Useful for deleting trees or evaluating expression trees.
Print or process node only after children are done.
Handles empty (null) nodes by returning immediately.

Full Transcript

Postorder tree traversal means visiting the left subtree first, then the right subtree, and finally the root node. The code recursively calls itself on the left child, then the right child, and prints the node's value last. The execution table shows each step visiting nodes D, E, B, F, G, C, and finally A in that order. When a node is null, the function returns immediately without printing. The call stack grows as recursion goes deeper and shrinks as nodes are visited. This traversal is useful when you need to process children before their parent, such as deleting nodes or evaluating expressions.

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 traversal order to options

   Left subtree, Right subtree, Root node correctly lists Left subtree, Right subtree, Root node order.

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 after children [OK]

Common Mistakes:

• Confusing postorder with preorder or inorder
• Visiting root before children
• Swapping left and right subtree order

2. Which of the following TypeScript function signatures correctly represents a postorder traversal of a binary tree node?

easy

A. function postorder(node: TreeNode | null): TreeNode[]

B. function postorder(node: TreeNode): number

C. function postorder(): TreeNode

D. function postorder(node: TreeNode | null): void

Solution

1. Step 1: Identify correct parameter and return type for traversal

   Traversal functions usually take a node or null and return void if printing or processing inline.

2. Step 2: Check options for correct signature

   function postorder(node: TreeNode | null): void takes a node or null and returns void, suitable for traversal printing or processing.

3. Final Answer:

   function postorder(node: TreeNode | null): void -> Option D

4. Quick Check:

   Traversal function signature = function postorder(node: TreeNode | null): void [OK]

Hint: Traversal usually takes node|null and returns void [OK]

Common Mistakes:

• Omitting null in parameter type
• Returning incorrect types like TreeNode or number
• Missing parameter in function signature

3. Given the following binary tree:

    1
   / \
  2   3
 / \
4   5

What is the output of a postorder traversal?

medium

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

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

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 visits 4, then 5, then 2.

2. Step 2: Traverse right subtree and root

   Right subtree is 3, visited next. Finally, root 1 is visited.

3. Final Answer:

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

4. Quick Check:

   Postorder output = [4, 5, 2, 3, 1] [OK]

Hint: Postorder prints children before parent [OK]

Common Mistakes:

• Visiting root before children
• Mixing left and right subtree order
• Confusing with preorder or inorder output

4. Consider this TypeScript postorder traversal function:

function postorder(node: TreeNode | null): void {
  if (!node) return;
  postorder(node.right);
  postorder(node.left);
  console.log(node.val);
}

What is the error in this code?

medium

A. It prints node value before children

B. It does not check for null nodes

C. It visits right subtree before left, reversing postorder

D. It returns a value but should be void

Solution

1. Step 1: Analyze traversal order in code

   The function calls postorder on right child first, then left child, then prints root.

2. Step 2: Compare with correct postorder order

   Correct postorder is left, right, root. This code reverses left and right order.

3. Final Answer:

   It visits right subtree before left, reversing postorder -> Option C

4. Quick Check:

   Left before right in postorder [OK]

Hint: Postorder = left first, then right, then root [OK]

Common Mistakes:

• Swapping left and right subtree calls
• Printing before visiting children
• Ignoring null checks

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

hard

A. function postorder(node: TreeNode | null, result: number[]): void {
if (!node) return;
result.push(node.val);
postorder(node.left, result);
postorder(node.right, result);
}

B. function postorder(node: TreeNode | null, result: number[]): void {
if (!node) return;
postorder(node.left, result);
postorder(node.right, result);
result.push(node.val);
}

C. function postorder(node: TreeNode | null, result: number[]): number[] {
if (!node) return result;
result.push(node.val);
postorder(node.left, result);
postorder(node.right, result);
return result;
}

D. function postorder(node: TreeNode | null): number[] {
if (!node) return [];
return [node.val, ...postorder(node.left), ...postorder(node.right)];
}

Solution

1. Step 1: Understand postorder traversal collection

   Postorder visits left, then right, then root. Values should be pushed after children.

2. Step 2: Check each option for correct order and pushing

   function postorder(node: TreeNode | null, result: number[]): void { if (!node) return; postorder(node.left, result); postorder(node.right, result); result.push(node.val); } visits left, right, then pushes node value, correctly collecting postorder.

3. Final Answer:

   function postorder(node: TreeNode | null, result: number[]): void { if (!node) return; postorder(node.left, result); postorder(node.right, result); result.push(node.val); } -> Option B

4. Quick Check:

   Push after children = postorder [OK]

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

Common Mistakes:

• Pushing node value before children
• Returning new arrays instead of using passed array
• Swapping left and right subtree calls