Tree Traversal Inorder Left Root Right in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of inorder traversal?

Given the binary tree below, what is the output of inorder traversal (Left, Root, Right)?

DSA Javascript

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

const root = new Node(10);
root.left = new Node(5);
root.right = new Node(15);
root.left.left = new Node(3);
root.left.right = new Node(7);

function inorder(node, result = []) {
  if (!node) return;
  inorder(node.left, result);
  result.push(node.value);
  inorder(node.right, result);
  return result;
}

console.log(inorder(root));

A [3, 5, 7, 10, 15]

B [10, 5, 3, 7, 15]

C [15, 10, 7, 5, 3]

D [5, 3, 7, 10, 15]

💡 Hint

Remember inorder means visit left child first, then root, then right child.

Inorder traversal visits nodes in the order: left subtree, root, right subtree.

For the given tree, the nodes are visited as 3 (leftmost), 5 (parent of 3 and 7), 7 (right child of 5), 10 (root), and 15 (right child of root).

❓ Predict Output

intermediate

Output of inorder traversal on a single node tree

What is the output of inorder traversal on a tree with only one node with value 42?

DSA Javascript

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

const root = new Node(42);

function inorder(node, result = []) {
  if (!node) return;
  inorder(node.left, result);
  result.push(node.value);
  inorder(node.right, result);
  return result;
}

console.log(inorder(root));

A [42]

B []

C [null]

D [0]

💡 Hint

A single node tree returns just that node's value in inorder.

Inorder traversal visits left, root, right. Since there are no children, only the root value 42 is returned.

🔧 Debug

advanced

Find the error in inorder traversal function

The following code is intended to perform inorder traversal but produces incorrect output. What is the error?

DSA Javascript

function inorder(node, result = []) {
  if (!node) return result;
  inorder(node.left, result);
  result.push(node.value);
  inorder(node.right, result);
  return result;
}

const root = { value: 1, left: null, right: null };
console.log(inorder(root));

A The function should push node.value before calling inorder on left child.

B The function does not check if node.left or node.right exist before calling inorder.

C The base case returns result instead of undefined, causing double returns.

D The function should not return result at all.

💡 Hint

Check what happens when node is null and what the function returns.

The base case returns the result array immediately when node is null. This causes the recursive calls to return early and skip some nodes.

The correct base case should return nothing (undefined) to allow recursion to continue properly.

❓ Predict Output

advanced

Inorder traversal output for unbalanced tree

What is the output of inorder traversal for the following unbalanced tree?

DSA Javascript

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

const root = new Node(8);
root.right = new Node(10);
root.right.right = new Node(14);
root.right.right.left = new Node(13);

function inorder(node, result = []) {
  if (!node) return;
  inorder(node.left, result);
  result.push(node.value);
  inorder(node.right, result);
  return result;
}

console.log(inorder(root));

A [8, 10, 14, 13]

B [14, 13, 10, 8]

C [10, 8, 13, 14]

D [8, 10, 13, 14]

💡 Hint

Remember inorder visits left subtree first, then root, then right subtree.

The traversal visits 8 (root), then moves to right subtree.

In right subtree, it visits left child 13, then 14, then 10.

So the order is 8, 10, 13, 14.

🧠 Conceptual

expert

How many nodes are visited in inorder traversal of a full binary tree with height 3?

Consider a full binary tree where every node has 0 or 2 children. If the tree height is 3 (root at height 1), how many nodes will inorder traversal visit?

A 3

B 7

C 15

D 8

💡 Hint

A full binary tree of height h has 2^h - 1 nodes.

A full binary tree of height 3 has 2^3 - 1 = 7 nodes.

Inorder traversal visits all nodes exactly once, so it visits 7 nodes.

Practice

1. What is the order of nodes visited in an inorder traversal of a binary tree?

easy

A. Root, Right subtree, Left subtree

B. Left subtree, Root, Right subtree

C. Right subtree, Root, Left subtree

D. Root, Left subtree, Right subtree

Solution

1. Step 1: Understand inorder traversal definition

   Inorder traversal visits nodes in the order: left subtree first, then the root node, and finally the right subtree.

2. Step 2: Match the traversal order to options

   Left subtree, Root, Right subtree correctly states the order as Left subtree, Root, Right subtree.

3. Final Answer:

   Left subtree, Root, Right subtree -> Option B

4. Quick Check:

   Inorder = Left, Root, Right [OK]

Hint: Inorder always visits left child before root [OK]

Common Mistakes:

• Confusing inorder with preorder or postorder
• Visiting root before left subtree
• Visiting right subtree before root

2. Which of the following is the correct JavaScript function signature for inorder traversal of a binary tree node named node?

easy

A. function inorder(node) { inorder(node.right); console.log(node.value); inorder(node.left); }

B. function inorder(node) { console.log(node.value); inorder(node.left); inorder(node.right); }

C. function inorder(node) { if(node) { inorder(node.left); console.log(node.value); inorder(node.right); } }

D. function inorder(node) { inorder(node.left); inorder(node.right); console.log(node.value); }

Solution

1. Step 1: Recall inorder traversal steps in code

   Inorder traversal visits left subtree, then root, then right subtree. So the function must call inorder on left, print root, then call inorder on right.

2. Step 2: Check each option's order

   function inorder(node) { if(node) { inorder(node.left); console.log(node.value); inorder(node.right); } } matches the correct order: left, root (console.log), right. Others have wrong orders.

3. Final Answer:

   function inorder(node) { if(node) { inorder(node.left); console.log(node.value); inorder(node.right); } } -> Option C

4. Quick Check:

   Left, Root, Right in code = function inorder(node) { if(node) { inorder(node.left); console.log(node.value); inorder(node.right); } } [OK]

Hint: Inorder prints after left call, before right call [OK]

Common Mistakes:

• Printing before left subtree traversal
• Swapping left and right subtree calls
• Missing null check for node

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

    10
   /  \
  5    15
 /    /  \
3    12  20

medium

A. [3, 5, 10, 12, 15, 20]

B. [10, 5, 3, 15, 12, 20]

C. [3, 5, 12, 10, 15, 20]

D. [5, 3, 10, 15, 12, 20]

Solution

1. Step 1: Traverse left subtree of root 10

   Left subtree of 10 is rooted at 5. Its left child is 3. Inorder of left subtree: visit 3, then 5 (root of subtree).

2. Step 2: Visit root 10 and then right subtree

   After left subtree, visit root 10. Then traverse right subtree rooted at 15: left child 12, root 15, right child 20. So inorder right subtree is 12, 15, 20.

3. Final Answer:

   [3, 5, 10, 12, 15, 20] -> Option A

4. Quick Check:

   Inorder = Left, Root, Right = [3,5,10,12,15,20] [OK]

Hint: List nodes left-root-right recursively [OK]

Common Mistakes:

• Visiting root before left subtree
• Mixing order of right subtree nodes
• Skipping leaf nodes

4. The following JavaScript code is intended to perform inorder traversal but has a bug. What is the bug?

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

medium

A. It prints the root before left subtree, so not inorder

B. It does not check for null nodes

C. It misses traversing the right subtree

D. It calls inorder on left and right in wrong order

Solution

1. Step 1: Analyze the order of operations in code

   The code prints node.value first, then calls inorder on left and right. This is preorder traversal order.

2. Step 2: Identify correct inorder order

   Inorder traversal requires visiting left subtree first, then printing root, then right subtree. The code prints root before left subtree, which is incorrect.

3. Final Answer:

   It prints the root before left subtree, so not inorder -> Option A

4. Quick Check:

   Print after left call for inorder [OK]

Hint: Print after left subtree call for inorder [OK]

Common Mistakes:

• Printing root before left subtree
• Confusing preorder with inorder
• Not checking for null nodes (though code does here)

5. You have a binary search tree (BST) and want to get all values in ascending order using inorder traversal. Which of the following modifications to the inorder traversal function will correctly collect values into an array instead of printing them?

function inorder(node, arr) {
  if (!node) return;
  // Fill missing code here
}

hard

A. inorder(node.left, arr); inorder(node.right, arr); arr.push(node.value);

B. arr.push(node.value); inorder(node.left, arr); inorder(node.right, arr);

C. inorder(node.right, arr); arr.push(node.value); inorder(node.left, arr);

D. inorder(node.left, arr); arr.push(node.value); inorder(node.right, arr);

Solution

1. Step 1: Recall inorder traversal order for BST

   Inorder traversal visits left subtree, then root, then right subtree, which returns values in ascending order for BST.

2. Step 2: Choose code that collects values in correct order

   inorder(node.left, arr); arr.push(node.value); inorder(node.right, arr); calls inorder on left, then pushes current node value, then calls inorder on right, correctly collecting values in ascending order.

3. Final Answer:

   inorder(node.left, arr); arr.push(node.value); inorder(node.right, arr); -> Option D

4. Quick Check:

   Left, Root, Right with push = inorder(node.left, arr); arr.push(node.value); inorder(node.right, arr); [OK]

Hint: Push after left call, before right call for sorted array [OK]

Common Mistakes:

• Pushing before left subtree traversal
• Swapping left and right subtree calls
• Pushing after both subtree traversals