DSA-VerseLearn by watching code run
DashboardData StructuresAlgorithmsVisualizerCORECoding PlaygroundInterview QuestionsComplexity AnalyzerLearning NotesBookmarksLearning ProgressSettings
All data structures

Non-Linear Data Structures

Binary Trees

A hierarchical structure where every node has at most two children: left and right.

Interactive1 visualizer(s)

1Introduction

Trees represent hierarchy — folders, organisation charts, HTML documents, expression parse trees. Binary trees, with at most two children per node, are the starting point for BSTs, heaps, segment trees and tries.

2What is it?

A binary tree is either empty or a node holding a value plus a left subtree and a right subtree, each of which is again a binary tree. The top node is the root; nodes without children are leaves.

3Why do we use it?

  • Represent hierarchical data naturally.
  • Balanced search trees give O(log n) search, insert and delete.
  • Recursive structure leads to short, elegant algorithms.
  • Heaps (complete binary trees) power priority queues.

4Real-world examples

  • File system folders.
  • Tournament brackets.
  • Expression trees in compilers: (a + b) * c.
  • Decision trees in machine learning.

5Internal working

Each node object stores value, left and right references. Missing children are null.

Traversals: preorder (Node-L-R), inorder (L-Node-R), postorder (L-R-Node) use recursion (or a stack); level order uses a queue.

Height h ranges from log₂ n (balanced) to n (skewed), and most operations cost O(h).

6Memory representation

The tree [4, 2, 6, 1, 3, 5, 7] (level order):

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

inorder:   1 2 3 4 5 6 7
preorder:  4 2 1 3 6 5 7
postorder: 1 3 2 5 7 6 4

7Operations

OperationHow it works
Traversal (any order)Visit each node once.
Height / sizeRecursive over all nodes.
Search (plain binary tree)May need to check every node.
Search (balanced BST)Go left or right at each level.
Insert / delete (balanced BST)Follow one root-to-leaf path.

8Visual explanation

Binary Tree Inorder Traversalinteractive Open full visualizer
4261357
result =[]
Current callOn the call stackBeing visitedVisited

Recursively visits the left subtree, then the node itself, then the right subtree (Left → Root → Right). On a Binary Search Tree this produces the values in sorted order.

1 / 67

9Code implementation

Complete, runnable programs (verified in all four languages). JavaScript and Python can be executed in the Coding Playground.

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

function inorder(node, result) {
  if (node === null) {
    return;
  }
  inorder(node.left, result);
  result.push(node.value);
  inorder(node.right, result);
}

function buildTree(values) {
  if (values.length === 0 || values[0] === null) return null;
  const root = new TreeNode(values[0]);
  const queue = [root];
  let i = 1;
  while (queue.length > 0 && i < values.length) {
    const node = queue.shift();
    if (i < values.length && values[i] !== null) {
      node.left = new TreeNode(values[i]);
      queue.push(node.left);
    }
    i++;
    if (i < values.length && values[i] !== null) {
      node.right = new TreeNode(values[i]);
      queue.push(node.right);
    }
    i++;
  }
  return root;
}

const root = buildTree([4, 2, 6, 1, 3, 5, 7]);
const result = [];
inorder(root, result);
console.log("Inorder:", result);

10Time complexity

OperationTime
Traversal (any order)O(n)
Height / sizeO(n)
Search (plain binary tree)O(n)
Search (balanced BST)O(log n)
Insert / delete (balanced BST)O(log n)

11Space complexity

Storing n nodes takes O(n). Recursive algorithms add O(h) call-stack space; level-order traversal needs O(w) queue space where w is the maximum width.

12Advantages

  • Models hierarchy directly.
  • Fast search when balanced.
  • Recursive algorithms are concise.

13Disadvantages

  • Can degrade to a linked list (O(n) operations) if unbalanced.
  • Pointer overhead per node.
  • Recursion can overflow on very deep trees.

14Common mistakes

  • Missing the null base case in recursion.
  • Confusing the three depth-first orders.
  • Assuming a binary tree is a BST.
  • Validating a BST by checking only immediate children instead of value ranges.

15Interview questions

Binary Tree Inorder TraversalEasy

16Practice exercises

  1. Compute the maximum depth of a tree.
  2. Check whether two trees are identical.
  3. Invert (mirror) a binary tree.
  4. Level order traversal returning a list per level.
  5. Lowest common ancestor of two nodes.

Try them in the Coding Playground.

On this page

  1. 01Introduction
  2. 02What is it?
  3. 03Why do we use it?
  4. 04Real-world examples
  5. 05Internal working
  6. 06Memory representation
  7. 07Operations
  8. 08Visual explanation
  9. 09Code implementation
  10. 10Time complexity
  11. 11Space complexity
  12. 12Advantages
  13. 13Disadvantages
  14. 14Common mistakes
  15. 15Interview questions
  16. 16Practice exercises