∞

Algo Infinity Verse

Master the Tree Data Structure Hierarchical Data & Traversal Techniques

|
Start Learning Practice Exercises
0 Topics
0 Examples
0 Exercises

🌳 Learn Trees

Master non-linear data structures to optimize search and hierarchical storage.

0 / 5 topics completed
01

Tree Terminology

Unlike arrays and linked lists which are linear data structures, a Tree is a hierarchical data structure. It consists of nodes connected by edges, commonly used to represent hierarchical relationships like file systems or organization charts.

Crucial Definitions

  • Node: An entity that contains a key or value and pointers to its child nodes.
  • Root: The topmost node of a tree. It has no parent.
  • Edge: The connecting link between any two nodes.
  • Leaf: A node that has no children (also called an external node).
  • Height of a Node: The number of edges on the longest path from the node to a leaf.
  • Depth of a Node: The number of edges from the root to the node.
02

Binary Trees

A Binary Tree is a special type of tree where each node can have a maximum of two children, typically distinguished as the "left child" and the "right child".

Types of Binary Trees

  • Full Binary Tree: Every node has either 0 or 2 children.
  • Complete Binary Tree: All levels are completely filled except possibly the last level, and all nodes are as far left as possible.
  • Perfect Binary Tree: All internal nodes have two children and all leaves are at the same level.
JavaScript 
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
03

Binary Search Trees (BST)

A Binary Search Tree (BST) is a node-based binary tree data structure which has the following strict properties (invariants):

The BST Invariant

  • The left subtree of a node contains only nodes with values lesser than the node’s value.
  • The right subtree of a node contains only nodes with values greater than the node’s value.
  • Both the left and right subtrees must also be binary search trees.

Because of this property, operations like Search, Insert, and Delete take $O(\log N)$ time on average. However, in the worst-case scenario (an unbalanced, skewed tree), the time complexity degrades to $O(N)$.

Python 
def searchBST(root, target):
    if root is None or root.val == target:
        return root
        
    if root.val < target:
        return searchBST(root.right, target)
        
    return searchBST(root.left, target)
04

Traversal Techniques

Tree Traversal refers to the process of visiting each node in the tree exactly once. Unlike arrays which are linearly traversed, trees can be traversed in multiple ways using Depth First Search (DFS).

1. In-order Traversal (Left, Root, Right)

Visits the left subtree, then the root node, then the right subtree. Crucial Note: In-order traversal of a BST gives nodes in non-decreasing (sorted) order.

JavaScript 
function inOrder(root) {
  if (root !== null) {
    inOrder(root.left);
    console.log(root.value);
    inOrder(root.right);
  }
}

2. Pre-order Traversal (Root, Left, Right)

Visits the root node first, then traverses the left subtree, and finally the right subtree. Use Case: Often used to create a copy (clone) of the tree or serialize it.

JavaScript 
function preOrder(root) {
  if (root !== null) {
    console.log(root.value);
    preOrder(root.left);
    preOrder(root.right);
  }
}

3. Post-order Traversal (Left, Right, Root)

Traverses the left subtree, then the right subtree, and visits the root node last. Use Case: Used to safely delete a tree (since it processes children before parents).

JavaScript 
function postOrder(root) {
  if (root !== null) {
    postOrder(root.left);
    postOrder(root.right);
    console.log(root.value);
  }
}
05

Practice Exercises

Test your understanding of tree properties, traversals, and time complexities.

Exercise 1: In-order Traversal Output

Given a Binary Search Tree (BST) with a root node of 10, a left child of 5, and a right child of 15, what is the output of an In-order traversal?

Answer: 5, 10, 15

Explanation: In-order traversal follows the Left -> Root -> Right pattern. It visits 5 (Left), then 10 (Root), then 15 (Right). Because it is a valid BST, an in-order traversal always results in sorted output.

Exercise 2: Identify the Root

You are given the Post-order traversal array of a binary tree: [4, 5, 2, 8, 9, 3, 1]. What is the root node of this tree?

Answer: 1

Explanation: Post-order traversal processes nodes in the order of Left -> Right -> Root. Therefore, the very last element processed and added to the output array is always the root of the tree.

Exercise 3: Maximum Nodes

What is the maximum number of nodes possible at level L of a binary tree? (Assume the root node is at Level 0).

Answer: $2^L$

Explanation: At Level 0 (root), there is $2^0 = 1$ node. At Level 1, there are $2^1 = 2$ nodes. At Level 2, there are $2^2 = 4$ nodes. The number of nodes doubles at each subsequent level.

Exercise 4: Worst-Case Deletion

What is the worst-case time complexity of searching for and deleting a node in an unbalanced Binary Search Tree of N nodes?

Answer: O(N)

Explanation: In the worst-case scenario (e.g., a tree where every node only has a right child), the tree degrades into a straight line resembling a linked list. Traversing it to find the target node will take linear time, O(N).