Boundary Traversal of Binary Tree in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Boundary Traversal on a Simple Binary Tree

What is the output of the boundary traversal for the given binary tree?

DSA Javascript

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

function boundaryTraversal(root) {
  if (!root) return [];
  const result = [];

  function isLeaf(node) {
    return !node.left && !node.right;
  }

  function addLeftBoundary(node) {
    let curr = node.left;
    while (curr) {
      if (!isLeaf(curr)) result.push(curr.data);
      if (curr.left) curr = curr.left;
      else curr = curr.right;
    }
  }

  function addLeaves(node) {
    if (isLeaf(node)) {
      result.push(node.data);
      return;
    }
    if (node.left) addLeaves(node.left);
    if (node.right) addLeaves(node.right);
  }

  function addRightBoundary(node) {
    let curr = node.right;
    const temp = [];
    while (curr) {
      if (!isLeaf(curr)) temp.push(curr.data);
      if (curr.right) curr = curr.right;
      else curr = curr.left;
    }
    for (let i = temp.length - 1; i >= 0; i--) {
      result.push(temp[i]);
    }
  }

  if (!isLeaf(root)) result.push(root.data);
  addLeftBoundary(root);
  addLeaves(root);
  addRightBoundary(root);

  return result;
}

// Tree construction
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);

console.log(boundaryTraversal(root));

A [1, 2, 4, 5, 6, 7, 3]

B [1, 2, 4, 5, 7, 6, 3]

C [1, 2, 4, 5, 6, 3, 7]

D [1, 4, 5, 6, 7, 2, 3]

💡 Hint

Remember to include left boundary (excluding leaves), all leaves, then right boundary in reverse order.

The boundary traversal includes the root (1), left boundary nodes excluding leaves (2), all leaf nodes in left to right order (4, 5, 6, 7), and right boundary nodes excluding leaves in reverse order (3).

❓ Predict Output

intermediate

Boundary Traversal Output for Left Skewed Tree

What will be the output of the boundary traversal for this left skewed binary tree?

DSA Javascript

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

function boundaryTraversal(root) {
  if (!root) return [];
  const result = [];

  function isLeaf(node) {
    return !node.left && !node.right;
  }

  function addLeftBoundary(node) {
    let curr = node.left;
    while (curr) {
      if (!isLeaf(curr)) result.push(curr.data);
      if (curr.left) curr = curr.left;
      else curr = curr.right;
    }
  }

  function addLeaves(node) {
    if (isLeaf(node)) {
      result.push(node.data);
      return;
    }
    if (node.left) addLeaves(node.left);
    if (node.right) addLeaves(node.right);
  }

  function addRightBoundary(node) {
    let curr = node.right;
    const temp = [];
    while (curr) {
      if (!isLeaf(curr)) temp.push(curr.data);
      if (curr.right) curr = curr.right;
      else curr = curr.left;
    }
    for (let i = temp.length - 1; i >= 0; i--) {
      result.push(temp[i]);
    }
  }

  if (!isLeaf(root)) result.push(root.data);
  addLeftBoundary(root);
  addLeaves(root);
  addRightBoundary(root);

  return result;
}

// Left skewed tree
const root = new Node(10);
root.left = new Node(20);
root.left.left = new Node(30);
root.left.left.left = new Node(40);

console.log(boundaryTraversal(root));

A [10, 40, 30, 20]

B [10, 20, 30]

C [40, 30, 20, 10]

D [10, 20, 30, 40]

💡 Hint

In a left skewed tree, left boundary and leaves overlap.

The root (10) is included first. The left boundary nodes excluding leaves are 20 and 30. The leaf node is 40. No right boundary nodes exist. So the traversal is [10, 20, 30, 40].

🔧 Debug

advanced

Identify the Bug in Boundary Traversal Code

The following code attempts to perform boundary traversal but produces incorrect output. What is the bug?

DSA Javascript

function addRightBoundary(node) {
  let curr = node.right;
  const temp = [];
  while (curr) {
    if (!isLeaf(curr)) temp.push(curr.data);
    if (curr.left) curr = curr.left;
    else curr = curr.right;
  }
  for (let i = temp.length - 1; i >= 0; i--) {
    result.push(temp[i]);
  }
}

A The function should start from node.left instead of node.right.

B The traversal of right boundary should prioritize right child first, not left child.

C The temp array should be reversed before pushing to result, but it is not reversed.

D The function should add leaves inside the loop, not outside.

💡 Hint

Check the order of child traversal in right boundary collection.

Right boundary traversal should move down the right child first to get the correct boundary nodes. The code incorrectly moves down the left child first, causing wrong nodes to be collected.

🧠 Conceptual

advanced

Understanding Leaf Node Identification in Boundary Traversal

In boundary traversal, why is it important to check if a node is a leaf before adding it to the left or right boundary?

A To avoid adding leaf nodes twice since leaves are added separately in the traversal.

B Because leaf nodes do not belong to the boundary of the tree.

C To ensure leaf nodes are only added in the right boundary traversal.

D To skip leaf nodes entirely from the traversal.

💡 Hint

Think about how leaves are handled separately in the traversal.

Leaf nodes are added once during the leaf collection step. Checking if a node is leaf before adding it to left or right boundary prevents duplication.

❓ Predict Output

expert

Boundary Traversal Output for Complex Tree with Missing Children

What is the output of the boundary traversal for the following binary tree?

DSA Javascript

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

function boundaryTraversal(root) {
  if (!root) return [];
  const result = [];

  function isLeaf(node) {
    return !node.left && !node.right;
  }

  function addLeftBoundary(node) {
    let curr = node.left;
    while (curr) {
      if (!isLeaf(curr)) result.push(curr.data);
      if (curr.left) curr = curr.left;
      else curr = curr.right;
    }
  }

  function addLeaves(node) {
    if (isLeaf(node)) {
      result.push(node.data);
      return;
    }
    if (node.left) addLeaves(node.left);
    if (node.right) addLeaves(node.right);
  }

  function addRightBoundary(node) {
    let curr = node.right;
    const temp = [];
    while (curr) {
      if (!isLeaf(curr)) temp.push(curr.data);
      if (curr.right) curr = curr.right;
      else curr = curr.left;
    }
    for (let i = temp.length - 1; i >= 0; i--) {
      result.push(temp[i]);
    }
  }

  if (!isLeaf(root)) result.push(root.data);
  addLeftBoundary(root);
  addLeaves(root);
  addRightBoundary(root);

  return result;
}

// Complex tree
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.right = new Node(4);
root.left.right.left = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.right.right.left = new Node(8);

console.log(boundaryTraversal(root));

A [1, 2, 4, 5, 6, 7, 3, 8]

B [1, 2, 5, 4, 6, 8, 7, 3]

C [1, 2, 4, 5, 6, 8, 7, 3]

D [1, 2, 4, 5, 6, 7, 8, 3]

💡 Hint

Remember to add left boundary excluding leaves, then all leaves, then right boundary in reverse order.

The left boundary excluding leaves is [2, 4]. Leaves are [5, 6, 8]. Right boundary excluding leaves in reverse order is [7, 3]. Root is 1. So combined: [1, 2, 4, 5, 6, 8, 7, 3].