ā¤ Like
šŸ”– Save
šŸ”— Share
Eric Hu
Eric Hu

DSA Tree Structure

@thedevspaceio

šŸŒ³ Trees Cheatsheet

Trees are hierarchical data structures with a root and child nodes. This cheatsheet covers binary trees, BSTs, traversals, and common operations.

āœ… Tree terminology āœ… Binary trees āœ… Binary search trees āœ… DFS traversals āœ… BFS level order āœ… Common operations

#dsa #trees #binarytree #bst #traversal #interview #coding #tips

A tree is a hierarchical structure of nodes connected by edges, with one root and no cycles.

Terminology

Tree

TermMeaning
RootThe top node (8).
LeafA node with no children (1, 4, 7, 14).
HeightLongest path from a node to a leaf.
DepthDistance from the root to a node.
SubtreeA node and all its descendants.

Binary search tree (BST)

Binary trees have at most two children per node.

BST

A binary tree where left children are smaller and right children are larger. Enables O(log n) search when balanced.

Every left descendant < node < every right descendant.

Depth-first traversals

Three ways to visit every node depth-first.

TraversalOrder
InorderLeft, node, right
PreorderNode, left, right
PostorderLeft, right, node
js
function inorder(node, result = []) {
  if (!node) return result;
  inorder(node.left, result);
  result.push(node.value);
  inorder(node.right, result);
  return result;
}
js
function preorder(node, result = []) {
  if (!node) return result;
  result.push(node.value);
  preorder(node.left, result);
  preorder(node.right, result);
  return result;
}
js
function postorder(node, result = []) {
  if (!node) return result;
  postorder(node.left, result);
  postorder(node.right, result);
  result.push(node.value);
  return result;
}

Breadth-first traversal

Visit nodes level by level with a queue.

js
function levelOrder(root) {
  if (!root) return [];
 
  const result = [];
  const queue = [root];
 
  while (queue.length > 0) {
    const level = [];
    const size = queue.length;
 
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.value);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
 
    result.push(level);
  }
 
  return result;
}

BST operations

Search a BST:

js
// Find a node with the target value
function search(node, target) {
  // Base case: not found, or found it
  if (!node || node.value === target) return node;
 
  // Go left if smaller, right if larger
  return target < node.value
    ? search(node.left, target)
    : search(node.right, target);
}

Insert at the correct leaf position:

js
// Insert a value into the BST
function insert(node, value) {
  // Found the empty spot, create the node
  if (!node) return { value, left: null, right: null };
 
  // Go left if smaller, right if larger
  if (value < node.value) node.left = insert(node.left, value);
  else node.right = insert(node.right, value);
 
  return node;
}

Delete a node while keeping the BST property:

js
// Delete a value from the BST
function remove(node, value) {
  if (!node) return null;
 
  // Find the node to delete
  if (value < node.value) {
    node.left = remove(node.left, value);
    return node;
  }
  if (value > node.value) {
    node.right = remove(node.right, value);
    return node;
  }
 
  // Case 1: no children, just remove it
  if (!node.left && !node.right) return null;
 
  // Case 2: one child, replace with the child
  if (!node.left) return node.right;
  if (!node.right) return node.left;
 
  // Case 3: two children, replace with the inorder successor
  // (smallest value in the right subtree)
  let successor = node.right;
  while (successor.left) successor = successor.left;
 
  node.value = successor.value;
  node.right = remove(node.right, successor.value);
  return node;
}

Full-Stack AI Developer Roadmap

From HTML & CSS to working with AI models, all in one structured roadmap.

@thedevspaceio
www.thedevspace.io