What is a Binary Tree?

A Binary Tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.

The Root is the top-most node of the tree. A Leaf is a node that has no children (the "ends" of the branches).

What is the "Height" of a tree?

Tree Height is the number of edges on the longest path from the root to a leaf node.

Binary Tree

A binary tree is a hierarchical structure in which each element has at most two children, referred to as the left child and the right child.

ANY

Any binary tree: every node has at most two children, and nothing else is promised.

Shape

Intuition

A hierarchical structure where each element has at most two children, referred to as the left child and the right child.

Concept

The foundation of many advanced data structures like BST, Heaps, and AVL Trees. There are several variations: Full (0 or 2 children), Perfect (all levels filled), Complete (filled level by level), Balanced (height diff ≤ 1), and Skewed (degenerate tree).

How it Works

Root: Topmost node.
Child: Node connected downwards.
Leaf: Node with no children.
Height: Longest path from node to leaf.
Depth: Path length from root to node.

Step-by-Step Breakdown

Common Operations:

Traversal: Visiting nodes (Pre-order, In-order, Post-order, Level-order).
Insertion: Adding a node (logic varies by tree type).
Deletion: Removing a node (often replacing with leaf or child).
Height/Depth: Calculating tree metrics.

When to Use

Representing hierarchical data (file systems, HTML DOM).
Decision trees.
Expression parsers.
Binary Heaps (Complete Trees).

When NOT to Use

When data is linear (use Array/Linked List).
When relationships are complex/cyclic (use Graph).

How to Identify

Any tree structure where max degree of any node is 2.

AI resume checker — match your resume to the job description

Tree Traversal

Binary Search Tree

Complexity

Time (Best)

O(1)

Time (Average)

O(n)

Time (Worst)

O(n)

Space

O(n)

Binary Tree Code

1// Intro: Node Definition
2class TreeNode {
3    constructor(val) {
4        this.val = val;
5        this.left = null;
6        this.right = null;
7    }
8}
9
10// 1. Full Tree: Every node has 0 or 2 children
11function isFull(root) {
12    if (!root) return true;
13    if (!root.left && !root.right) return true;
14    if (root.left && root.right) return isFull(root.left) && isFull(root.right);
15    return false;
16}
17
18// 2. Perfect Tree: All internal nodes have 2 children, leaves at same level
19function isPerfect(root) {
20    let depth = 0, node = root;
21    while (node) { depth++; node = node.left; }
22    function check(n, d, level) {
23        if (!n) return true;
24        if (!n.left && !n.right) return d === level + 1;
25        if (!n.left || !n.right) return false;
26        return check(n.left, d, level + 1) && check(n.right, d, level + 1);
27    }
28    return check(root, depth, 0);
29}
30
31// 3. Complete Tree: Levels filled left to right
32function isComplete(root) {
33    if (!root) return true;
34    let queue = [root], foundNull = false;
35    while (queue.length) {
36        let node = queue.shift();
37        if (!node) foundNull = true;
38        else {
39            if (foundNull) return false;
40            queue.push(node.left);
41            queue.push(node.right);
42        }
43    }
44    return true;
45}
46
47// 4. Balanced Tree: Height diff <= 1
48function isBalanced(root) {
49    function dfs(n) {
50        if (!n) return 0;
51        let l = dfs(n.left);
52        if (l === -1) return -1;
53        let r = dfs(n.right);
54        if (r === -1) return -1;
55        if (Math.abs(l - r) > 1) return -1;
56        return Math.max(l, r) + 1;
57    }
58    return dfs(root) !== -1;
59}
60
61// 5. Skewed Tree: Max 1 child per node
62function isSkewed(root) {
63    if (!root) return true;
64    if (root.left && root.right) return false;
65    return isSkewed(root.left) && isSkewed(root.right);
66}

Related Lessons

Binary Tree

Intuition

Concept

How it Works

Step-by-Step Breakdown

When to Use

When NOT to Use

How to Identify

Sample Problems

Maximum Depth of Binary Tree

Diameter of Binary Tree

Invert Binary Tree

Check Completeness of a Binary Tree

Balanced Binary Tree

AI resume checker — match your resume to the job description

Stack

Queue

Deque

Circular Queue

Frequently Asked Questions

What is a Binary Tree?

Root vs Leaf nodes?

What is the "Height" of a tree?