Boundary Traversal of Binary Tree in DSA Typescript - Build from Scratch

Boundary Traversal of Binary Tree

📖 Scenario: Imagine you have a family tree represented as a binary tree. You want to visit all the family members who are on the outer edge of the tree, starting from the top ancestor, going down the left side, then the bottom members from left to right, and finally up the right side.

🎯 Goal: Build a TypeScript program that performs a boundary traversal of a binary tree. The program will print the nodes on the boundary in the correct order: root, left boundary (excluding leaves), all leaves, and right boundary (excluding leaves) in reverse.

📋 What You'll Learn

Create a binary tree node class called TreeNode with val, left, and right properties

Create a binary tree with the exact structure given

Create a helper variable result as an array to store boundary nodes

Implement functions to add left boundary, leaves, and right boundary nodes

Perform the boundary traversal and store nodes in result

Print the result array as a sequence of node values separated by ' -> '

💡 Why This Matters

🌍 Real World

Boundary traversal is useful in graphical applications, tree visualization, and understanding the outer structure of hierarchical data.

💼 Career

Understanding tree traversals is essential for software engineers working with data structures, algorithms, and system design.

1

Create the Binary Tree Structure

Create a class called TreeNode with a constructor that takes a number val and initializes left and right as null. Then create the binary tree with this exact structure:

Root node value 20
Left child of root 8
Right child of root 22
Left child of node 8 is 4
Right child of node 8 is 12
Left child of node 12 is 10
Right child of node 12 is 14
Right child of node 22 is 25

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

// Create the binary tree nodes and link them
// Your code here

Hint

Start by defining the TreeNode class. Then create each node exactly as described and connect them using the left and right properties.

2

Create the Result Array for Boundary Nodes

Create a variable called result and initialize it as an empty array of numbers. This array will store the values of the boundary nodes in order.

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const root = new TreeNode(20);
root.left = new TreeNode(8);
root.right = new TreeNode(22);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(12);
root.left.right.left = new TreeNode(10);
root.left.right.right = new TreeNode(14);
root.right.right = new TreeNode(25);

// Create an empty array called result to store boundary nodes
// Your code here

Hint

Use const result: number[] = []; to create an empty array that will hold the boundary node values.

3

Implement Boundary Traversal Logic

Implement the boundary traversal by writing these functions:
1. isLeaf(node: TreeNode | null): boolean that returns true if the node has no children.
2. addLeftBoundary(node: TreeNode | null) that adds left boundary nodes (excluding leaves) to result.
3. addLeaves(node: TreeNode | null) that adds all leaf nodes to result.
4. addRightBoundary(node: TreeNode | null) that adds right boundary nodes (excluding leaves) to result in reverse order.

Then call these functions in order to perform the boundary traversal starting from root. Add root.val to result first if it is not a leaf.

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const root = new TreeNode(20);
root.left = new TreeNode(8);
root.right = new TreeNode(22);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(12);
root.left.right.left = new TreeNode(10);
root.left.right.right = new TreeNode(14);
root.right.right = new TreeNode(25);

const result: number[] = [];

// Implement isLeaf, addLeftBoundary, addLeaves, addRightBoundary functions
// Perform boundary traversal by calling these functions
// Your code here

Hint

Write helper functions to check if a node is a leaf, add left boundary nodes, add leaf nodes, and add right boundary nodes in reverse. Then call them in order, adding the root value first if it is not a leaf.

4

Print the Boundary Traversal Result

Print the result array as a string where node values are joined by ' -> '. Use console.log to display the boundary traversal sequence.

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const root = new TreeNode(20);
root.left = new TreeNode(8);
root.right = new TreeNode(22);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(12);
root.left.right.left = new TreeNode(10);
root.left.right.right = new TreeNode(14);
root.right.right = new TreeNode(25);

const result: number[] = [];

function isLeaf(node: TreeNode | null): boolean {
  return node !== null && node.left === null && node.right === null;
}

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

function addLeaves(node: TreeNode | null): void {
  if (node === null) return;
  if (isLeaf(node)) {
    result.push(node.val);
    return;
  }
  addLeaves(node.left);
  addLeaves(node.right);
}

function addRightBoundary(node: TreeNode | null): void {
  const temp: number[] = [];
  let curr = node;
  while (curr !== null) {
    if (!isLeaf(curr)) temp.push(curr.val);
    if (curr.right !== null) {
      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.val);
addLeftBoundary(root.left);
addLeaves(root);
addRightBoundary(root.right);

// Print the boundary traversal result
// Your code here

Hint

Use console.log(result.join(' -> ')); to print the boundary traversal nodes separated by arrows.

Practice

1. What is the main purpose of Boundary Traversal in a binary tree?

easy

A. To print all leaf nodes only

B. To print all nodes on the boundary in anti-clockwise direction

C. To print nodes level by level

D. To print nodes in in-order traversal

Solution

1. Step 1: Understand boundary traversal definition

   Boundary traversal prints nodes on the edges of the tree, including left boundary, leaves, and right boundary.

2. Step 2: Identify traversal direction

   The traversal is done in anti-clockwise direction starting from root, left boundary, leaves, then right boundary.

3. Final Answer:

   To print all nodes on the boundary in anti-clockwise direction -> Option B

4. Quick Check:

   Boundary traversal = anti-clockwise boundary nodes [OK]

Hint: Boundary traversal prints edges anti-clockwise [OK]

Common Mistakes:

• Confusing boundary traversal with leaf node traversal
• Thinking it prints nodes level-wise
• Assuming it prints in-order nodes

2. Which of the following TypeScript function signatures correctly represents a function to perform boundary traversal of a binary tree?

easy

A. function boundaryTraversal(): number[]

B. function boundaryTraversal(root: TreeNode): void

C. function boundaryTraversal(root: TreeNode, result: number[]): void

D. function boundaryTraversal(root: TreeNode): number[]

Solution

1. Step 1: Analyze function purpose

   The function should take the root node and return an array of numbers representing boundary nodes.

2. Step 2: Check signatures

   function boundaryTraversal(root: TreeNode): number[] takes root and returns number array, matching expected usage. function boundaryTraversal(root: TreeNode): void returns void, so no output. function boundaryTraversal(root: TreeNode, result: number[]): void requires external array input, less common. function boundaryTraversal(): number[] has no input, so invalid.

3. Final Answer:

   function boundaryTraversal(root: TreeNode): number[] -> Option D

4. Quick Check:

   Function returns boundary nodes array [OK]

Hint: Function should return array of boundary nodes [OK]

Common Mistakes:

• Using void return type without output
• Missing root parameter
• Expecting external array input unnecessarily

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

      1
     / \
    2   3
   / \   \
  4   5   6
     / \  /
    7  8 9

medium

A. [1, 2, 4, 7, 8, 9, 6]

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

C. [1, 2, 4, 7, 8, 9, 6, 3]

D. [1, 2, 4, 7, 8, 9, 3, 6]

Solution

1. Step 1: Identify left boundary nodes

   Left boundary excluding leaves: 1, 2

2. Step 2: Identify leaf nodes left to right

   Leaves: 4, 7, 8, 9, 6

3. Step 3: Identify right boundary nodes bottom to top excluding leaves

   Right boundary: 3

4. Step 4: Combine in anti-clockwise order

   Boundary = left boundary + leaves (excluding duplicates) + right boundary = [1, 2, 4, 7, 8, 9, 6, 3]

5. Final Answer:

   [1, 2, 4, 7, 8, 9, 6, 3] -> Option C

6. Quick Check:

   Boundary traversal = [1,2,4,7,8,9,6,3] [OK]

Hint: Combine left boundary, leaves, right boundary anti-clockwise [OK]

Common Mistakes:

• Including leaf nodes twice
• Wrong order of right boundary nodes
• Missing root or boundary nodes

4. Consider the following TypeScript code snippet for boundary traversal. What is the bug?

function printBoundary(root: TreeNode | null) {
  if (!root) return;
  console.log(root.val);
  printLeftBoundary(root.left);
  printLeaves(root.left);
  printLeaves(root.right);
  printRightBoundary(root.right);
}

function printLeftBoundary(node: TreeNode | null) {
  if (!node || (!node.left && !node.right)) return;
  console.log(node.val);
  if (node.left) printLeftBoundary(node.left);
  else printLeftBoundary(node.right);
}

function printRightBoundary(node: TreeNode | null) {
  if (!node || (!node.left && !node.right)) return;
  if (node.right) printRightBoundary(node.right);
  else printRightBoundary(node.left);
  console.log(node.val);
}

medium

A. Left boundary includes leaf nodes which should be excluded

B. Root node is printed twice

C. Right boundary nodes are printed before recursive calls, causing wrong order

D. Leaves are printed twice because printLeaves is called on both left and right subtrees

Solution

1. Step 1: Analyze left boundary function

   printLeftBoundary prints node.val even if node is leaf, but leaves should be excluded from left boundary.

2. Step 2: Check leaf exclusion condition

   Condition (!node.left && !node.right) returns early, so leaves are excluded from printing in left boundary, so no bug here.

3. Step 3: Re-examine leaf printing calls

   printLeaves is called separately on left and right subtrees, so leaves are printed once only.

4. Step 4: Check right boundary printing order

   Right boundary prints after recursive calls, which is correct for bottom-up order.

5. Step 5: Identify actual bug

   Left boundary function prints node.val before recursive call, so leaf nodes on left boundary get printed twice: once in left boundary and once in leaves.

6. Final Answer:

   Left boundary includes leaf nodes which should be excluded -> Option A

7. Quick Check:

   Leaf nodes must not print in left boundary [OK]

Hint: Exclude leaves from left/right boundary printing [OK]

Common Mistakes:

• Printing leaves twice
• Printing right boundary in wrong order
• Printing root twice

5. You want to modify boundary traversal to print nodes in clockwise order starting from root. Which change is correct?

hard

A. Print root, then right boundary top-down, then leaves right to left, then left boundary bottom-up

B. Print root, then left boundary top-down, then leaves left to right, then right boundary bottom-up

C. Print root, then leaves left to right, then left boundary top-down, then right boundary bottom-up

D. Print root, then right boundary bottom-up, then leaves right to left, then left boundary top-down

Solution

1. Step 1: Understand clockwise boundary traversal order

   Clockwise traversal starts at root, then right boundary top-down, leaves right to left, then left boundary bottom-up.

2. Step 2: Match options with traversal order

   Print root, then right boundary top-down, then leaves right to left, then left boundary bottom-up matches this order exactly. Print root, then left boundary top-down, then leaves left to right, then right boundary bottom-up is anti-clockwise order. Options C and D mix orders incorrectly.

3. Final Answer:

   Print root, then right boundary top-down, then leaves right to left, then left boundary bottom-up -> Option A

4. Quick Check:

   Clockwise = root + right boundary + leaves + left boundary [OK]

Hint: Clockwise = root, right boundary, leaves, left boundary [OK]

Common Mistakes:

• Confusing clockwise with anti-clockwise order
• Printing boundaries in wrong direction
• Mixing leaf traversal order