Tree Traversal Postorder Left Right Root in DSA Javascript - 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 program that creates a small tree, sets up a function to visit nodes in postorder (left, right, root), and prints the names of family members in that order.

📋 What You'll Learn

Create a tree node structure with name, left, and right properties

Build a small tree with exactly three nodes: 'Grandpa' as root, 'Dad' as left child, and 'Uncle' as right child

Write a function called postorderTraversal that visits nodes in left-right-root order

Print the names of the nodes in the order they are visited

💡 Why This Matters

🌍 Real World

Tree traversal is used in many areas like file system navigation, organizing family trees, and evaluating expressions.

💼 Career

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

1

Create the tree nodes

Create three variables called grandpa, dad, and uncle. Each should be an object with a name property set to 'Grandpa', 'Dad', and 'Uncle' respectively, and left and right properties set to null.

DSA Javascript

// Your code here

Hint

Use object literals with name, left, and right keys.

2

Link the nodes to form the tree

Set the left property of grandpa to dad and the right property of grandpa to uncle.

DSA Javascript

const grandpa = { name: 'Grandpa', left: null, right: null };
const dad = { name: 'Dad', left: null, right: null };
const uncle = { name: 'Uncle', left: null, right: null };

// Your code here

Hint

Assign the dad and uncle objects to the left and right properties of grandpa.

3

Write the postorder traversal function

Write a function called postorderTraversal that takes a node as input. It should recursively visit the left child, then the right child, and finally print the name of the current node.

DSA Javascript

const grandpa = { name: 'Grandpa', left: null, right: null };
const dad = { name: 'Dad', left: null, right: null };
const uncle = { name: 'Uncle', left: null, right: null };

grandpa.left = dad;
grandpa.right = uncle;

// Your code here

Hint

Use recursion to visit left, then right, then print the node's name.

4

Run the traversal and print output

Call postorderTraversal with grandpa as the argument to print the names in postorder.

DSA Javascript

const grandpa = { name: 'Grandpa', left: null, right: null };
const dad = { name: 'Dad', left: null, right: null };
const uncle = { name: 'Uncle', left: null, right: null };

grandpa.left = dad;
grandpa.right = uncle;

function postorderTraversal(node) {
    if (node === null) {
        return;
    }
    postorderTraversal(node.left);
    postorderTraversal(node.right);
    console.log(node.name);
}

// Your code here

Hint

Call the function with grandpa to see the postorder output.

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