0
0
DSA Typescriptprogramming~20 mins

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

Choose your learning style9 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Challenge - 5 Problems
🎖️
Boundary Traversal Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate
2:00remaining
Output of Boundary Traversal on a Simple Binary Tree
What is the output of the boundary traversal for the given binary tree?
DSA Typescript
class Node {
  constructor(public data: number, public left: Node | null = null, public right: Node | null = null) {}
}

function boundaryTraversal(root: Node | null): number[] {
  if (!root) return [];

  const result: number[] = [];

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

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

  function addLeaves(node: Node | null) {
    if (!node) return;
    if (isLeaf(node)) {
      result.push(node.data);
      return;
    }
    addLeaves(node.left);
    addLeaves(node.right);
  }

  function addRightBoundary(node: Node | null) {
    const temp: number[] = [];
    let curr = node;
    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.left);
  addLeaves(root);
  addRightBoundary(root.right);

  return result;
}

// Tree structure:
//       1
//      / \
//     2   3
//    / \   \
//   4   5   6
//      / \  /
//     7  8 9

const root = new Node(1,
  new Node(2,
    new Node(4),
    new Node(5,
      new Node(7),
      new Node(8)
    )
  ),
  new Node(3,
    null,
    new Node(6,
      new Node(9),
      null
    )
  )
);

console.log(boundaryTraversal(root));
A[1, 2, 4, 7, 8, 9, 6]
B[1, 2, 4, 7, 8, 5, 9, 6, 3]
C[1, 2, 4, 7, 8, 9, 6, 3]
D[1, 4, 7, 8, 9, 6, 3]
Attempts:
2 left
💡 Hint
Remember to include left boundary (excluding leaves), all leaves, and right boundary (excluding leaves) in reverse order.
🧠 Conceptual
intermediate
1:30remaining
Understanding Boundary Traversal Components
Which of the following correctly describes the components included in the boundary traversal of a binary tree?
ARoot node, all nodes in left subtree, all leaf nodes, all nodes in right subtree
BRoot node and all nodes at the deepest level
COnly leaf nodes from left to right
DRoot node, left boundary excluding leaves, all leaf nodes, right boundary excluding leaves in reverse order
Attempts:
2 left
💡 Hint
Think about which nodes form the outer edge of the tree.
🔧 Debug
advanced
1:30remaining
Identify the Error in Boundary Traversal Code
Given the following code snippet for boundary traversal, what error will it produce when run on a non-empty tree?
DSA Typescript
function addLeftBoundary(node) {
  let curr = node;
  while (curr) {
    if (!isLeaf(curr)) result.push(curr.data);
    if (curr.left) curr = curr.left;
    else curr = curr.right;
  }
}

// Assume isLeaf and result are defined globally

addLeftBoundary(null);
ANo error, function completes silently
BTypeError: Cannot read property 'left' of null
CReferenceError: isLeaf is not defined
DInfinite loop
Attempts:
2 left
💡 Hint
Consider what happens when the input node is null.
❓ Predict Output
advanced
2:00remaining
Boundary Traversal Output for Skewed Tree
What is the output of the boundary traversal for the following skewed binary tree?
DSA Typescript
// Tree structure:
// 1
//  \
//   2
//    \
//     3
//      \
//       4

class Node {
  constructor(public data: number, public left: Node | null = null, public right: Node | null = null) {}
}

const root = new Node(1, null, new Node(2, null, new Node(3, null, new Node(4))));

console.log(boundaryTraversal(root));

function boundaryTraversal(root: Node | null): number[] {
  if (!root) return [];

  const result: number[] = [];

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

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

  function addLeaves(node: Node | null) {
    if (!node) return;
    if (isLeaf(node)) {
      result.push(node.data);
      return;
    }
    addLeaves(node.left);
    addLeaves(node.right);
  }

  function addRightBoundary(node: Node | null) {
    const temp: number[] = [];
    let curr = node;
    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.left);
  addLeaves(root);
  addRightBoundary(root.right);

  return result;
}
A[1, 2, 3, 4]
B[1, 4, 3, 2]
C[1, 4]
D[1, 2, 3]
Attempts:
2 left
💡 Hint
In a skewed tree, left boundary might be empty; right boundary is reversed.
🚀 Application
expert
1:30remaining
Count Nodes in Boundary Traversal
Given a binary tree, how many nodes will be included in the boundary traversal if the tree is a perfect binary tree of height 3 (levels 0 to 3)?
A9
B12
C15
D10
Attempts:
2 left
💡 Hint
Count root, left boundary excluding leaves, leaves, and right boundary excluding leaves carefully.