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.