Tree Traversal Postorder Left Right Root in DSA Typescript - Build from Scratch

Tree Traversal Postorder Left Right Root

📖 Scenario: You are working with a simple family tree where each person can have up to two children. You want to visit all family members in a special order: first the left child, then the right child, and finally the parent. This order is called postorder traversal.

🎯 Goal: Build a small tree using nodes, then write a function to visit all nodes in postorder (left, right, root) and collect their names in an array.

📋 What You'll Learn

Create a TreeNode class with name, left, and right properties

Create a tree with root node named "Grandparent", left child "Parent1", and right child "Parent2"

Add children to "Parent1": left child "Child1" and right child "Child2"

Write a function postorderTraversal that takes a TreeNode and returns an array of names in postorder

Print the array returned by postorderTraversal when called on the root node

💡 Why This Matters

🌍 Real World

Tree traversal is used in many real-world applications like file system navigation, organizing family trees, and parsing expressions.

💼 Career

Understanding tree traversal is important for software developers working with hierarchical data, databases, and algorithms.

1

Create the TreeNode class and build the tree

Create a class called TreeNode with a constructor that takes a name string and optional left and right TreeNode parameters. Then create the tree nodes exactly as follows: root node named "Grandparent", left child named "Parent1", right child named "Parent2", and add children to "Parent1" named "Child1" (left) and "Child2" (right). Connect the nodes properly.

DSA Typescript

// Define TreeNode class and create the tree nodes
// Your code here

Hint

Start by defining the TreeNode class with name, left, and right. Then create each node and connect them as children.

2

Create an array to collect traversal results

Create an empty array called result of type string[] that will store the names of nodes visited during traversal.

DSA Typescript

class TreeNode {
    name: string;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(name: string, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.name = name;
        this.left = left;
        this.right = right;
    }
}

const child1 = new TreeNode("Child1");
const child2 = new TreeNode("Child2");
const parent1 = new TreeNode("Parent1", child1, child2);
const parent2 = new TreeNode("Parent2");
const grandparent = new TreeNode("Grandparent", parent1, parent2);

// Create an empty array called result to store node names
// Your code here

Hint

Just create an empty array named result to hold the names.

3

Write the postorderTraversal function

Write a function called postorderTraversal that takes a node of type TreeNode | null. If the node is not null, it should recursively call itself on the left child, then on the right child, and finally push the node.name into the result array.

DSA Typescript

class TreeNode {
    name: string;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(name: string, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.name = name;
        this.left = left;
        this.right = right;
    }
}

const child1 = new TreeNode("Child1");
const child2 = new TreeNode("Child2");
const parent1 = new TreeNode("Parent1", child1, child2);
const parent2 = new TreeNode("Parent2");
const grandparent = new TreeNode("Grandparent", parent1, parent2);

const result: string[] = [];

// Write the postorderTraversal function below
// Your code here

Hint

Use recursion: call postorderTraversal on left, then right, then add current node's name to result.

4

Call the function and print the result

Call postorderTraversal with the grandparent node. Then print the result array using console.log(result).

DSA Typescript

class TreeNode {
    name: string;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(name: string, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.name = name;
        this.left = left;
        this.right = right;
    }
}

const child1 = new TreeNode("Child1");
const child2 = new TreeNode("Child2");
const parent1 = new TreeNode("Parent1", child1, child2);
const parent2 = new TreeNode("Parent2");
const grandparent = new TreeNode("Grandparent", parent1, parent2);

const result: string[] = [];

function postorderTraversal(node: TreeNode | null): void {
    if (node !== null) {
        postorderTraversal(node.left);
        postorderTraversal(node.right);
        result.push(node.name);
    }
}

// Call postorderTraversal on grandparent and print result
// Your code here

Hint

Call postorderTraversal(grandparent) and then print result with console.log(result).

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