Binary Trees in DSA: Traversals, Properties & Applications

Master binary tree concepts, traversal techniques, and common problem patterns. This tutorial covers tree construction, recursive algorithms, and interview problems with implementation examples.

Binary Tree Usage in Systems (2023)

Search (35%)

Hierarchical Data (25%)

Decision Making (20%)

Other (20%)

1. Binary Tree Fundamentals

Core Concepts:

Node Structure: Value + Left/Right pointers
Root Node: Topmost node without parent
Leaf Node: Nodes without children
Height: Longest path from root to leaf

Binary Tree Types:

Type	Description	Example
Complete	All levels filled except last, left-filled	Heap structures
Full	Every node has 0 or 2 children	Expression trees
Perfect	All interior nodes have 2 children, all leaves same level	Balanced trees
Balanced	Height difference ≤1 for all subtrees	AVL trees

Node Implementation:


class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// Example tree construction
const tree = new TreeNode(1,
  new TreeNode(2,
    new TreeNode(4),
    new TreeNode(5)
  ),
  new TreeNode(3,
    null,
    new TreeNode(6)
  )
);

2. Tree Traversal Techniques

Depth-First Traversals:

Pre-order (Root-Left-Right)


function preorder(root) {
  if (!root) return [];
  return [
    root.val,
    ...preorder(root.left),
    ...preorder(root.right)
  ];
}

In-order (Left-Root-Right)


function inorder(root) {
  if (!root) return [];
  return [
    ...inorder(root.left),
    root.val,
    ...inorder(root.right)
  ];
}

Post-order (Left-Right-Root)


function postorder(root) {
  if (!root) return [];
  return [
    ...postorder(root.left),
    ...postorder(root.right),
    root.val
  ];
}

Breadth-First (Level-order):


function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  
  while (queue.length) {
    const levelSize = queue.length;
    const currentLevel = [];
    
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      currentLevel.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    
    result.push(currentLevel);
  }
  
  return result;
}

3. Binary Tree Properties

Key Algorithms:

Check Balanced


function isBalanced(root) {
  return checkHeight(root) !== -1;
  
  function checkHeight(node) {
    if (!node) return 0;
    
    const left = checkHeight(node.left);
    if (left === -1) return -1;
    
    const right = checkHeight(node.right);
    if (right === -1) return -1;
    
    if (Math.abs(left - right) > 1) return -1;
    return Math.max(left, right) + 1;
  }
}

Validate BST


function isValidBST(root) {
  return validate(root, -Infinity, Infinity);
  
  function validate(node, min, max) {
    if (!node) return true;
    if (node.val <= min || node.val >= max) return false;
    return validate(node.left, min, node.val) && 
           validate(node.right, node.val, max);
  }
}

Common Calculations:

Height: Max depth from root to leaf
Diameter: Longest path between any two nodes
Count Nodes: Total nodes in tree
Max Path Sum: Highest sum path (can include negatives)

Binary Tree Problem-Solving Cheat Sheet

Problem Type	Approach	Time Complexity
Path Sum	DFS with backtracking	O(n)
Lowest Common Ancestor	Post-order traversal	O(n)
Tree Construction	In-order + Pre/Post-order	O(n)
Vertical Order	BFS with column tracking	O(n)

4. Advanced Binary Tree Concepts

Threaded Binary Trees

Optimized for in-order traversal


class ThreadedNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
    this.leftThread = false; // true if left is thread
    this.rightThread = false; // true if right is thread
  }
}

Morris Traversal

In-order with O(1) space


function morrisInorder(root) {
  let current = root;
  const result = [];
  
  while (current) {
    if (!current.left) {
      result.push(current.val);
      current = current.right;
    } else {
      let predecessor = current.left;
      while (predecessor.right && predecessor.right !== current) {
        predecessor = predecessor.right;
      }
      
      if (!predecessor.right) {
        predecessor.right = current;
        current = current.left;
      } else {
        predecessor.right = null;
        result.push(current.val);
        current = current.right;
      }
    }
  }
  
  return result;
}

Serialize/Deserialize

Tree to string and back


function serialize(root) {
  if (!root) return 'null';
  return `${root.val},${serialize(root.left)},${serialize(root.right)}`;
}

function deserialize(data) {
  const nodes = data.split(',');
  return build();
  
  function build() {
    const val = nodes.shift();
    if (val === 'null') return null;
    const node = new TreeNode(Number(val));
    node.left = build();
    node.right = build();
    return node;
  }
}

Binary Tree Problem-Solving Checklist

✓ Handle null/leaf node cases first

✓ Choose appropriate traversal (DFS/BFS)

✓ Consider recursive vs iterative approach

✓ Track additional state when needed (parent refs, depth)

DSA Expert Insight: Binary tree problems appear in 40% of technical interviews. Mastering recursive traversal and subtree analysis is key to solving most tree-based problems efficiently.

0 Interaction

0 Views

0 Likes