Trees

Binary Tree Properties

What is a Binary Tree?

A Binary Tree is a hierarchical structure built from nodes, where every node has at most two children, conventionally called the left and right child. That two-child limit is what separates it from a general tree, and it's what makes every property below meaningful and calculable.

Key Terminology

Root: The single node at the top of the tree with no parent.
Parent / Child: A node directly connected one level above/below another.
Sibling: Nodes that share the same parent.
Leaf: A node with no children (both left and right are null).
Internal Node: Any node with at least one child (includes the root).
Edge: The connection/link between a parent and its child.
Depth of a node: Number of edges from the root down to that node.
Height of a node: Number of edges on the longest path from that node down to a leaf.
Height of the tree: The height of the root node — the longest root-to-leaf path.

Height, Depth & Level

Height and depth are the two measurements that come up constantly when reasoning about a tree's performance — most tree operations run in time proportional to the height, not the number of nodes, which is exactly why keeping a tree balanced matters so much.

Depth 0Depth 1Depth 2ABCDEFG
Internal nodeLeaf node

In this tree, node A sits at depth 0 (the root), B and C sit at depth 1, and D, E, F, G all sit at depth 2. Since the deepest node is at depth 2, the tree's height is 2.

Node Count Formulas

PropertyFormula
Max nodes at depth d2^d
Max total nodes for height h2^(h+1) − 1
Min total nodes for height hh + 1
Min possible height for n nodes⌊log₂ n⌋

Why Balance Matters

  • Balanced tree, n = 7 nodes → height = 2 (as close to log₂ 7 as possible)
  • Skewed tree, n = 7 nodes → height = 6 (every node has exactly one child)
  • Same node count, wildly different performance — height is what actually matters

Complexity Implications

Since most tree operations (search, insert, delete) walk from the root down to a leaf, their time complexity is O(height) — O(log n) for a balanced tree, degrading to O(n) for a skewed one.

Time Complexity Analysis

Advertisement

Space Complexity for storing a binary tree with n nodes is O(n), since each node needs a fixed amount of memory (its value plus two child pointers) regardless of the tree's shape.

These structural properties aren't just theory — they're what a balancing algorithm (like in AVL or Red-Black trees) is actively trying to protect. A tree that's allowed to grow unchecked can degrade to the same O(n) worst case as a linked list.

Daily DSA Challenge by Scale Engineer

Build a tree and watch its height, depth, and node counts update live

Tree is empty
Height
—
Total Nodes
0
Leaf Nodes
0
No tree yet — insert a value or generate a random tree
Internal nodeLeaf nodeRootd0, d1, d2… = depth from root

Test Your Knowledge before moving forward!

Binary Tree Properties Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Binary Tree Height & Node Count

// Binary Tree node
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Height: number of edges on the longest root-to-leaf path
function height(node) {
  if (node === null) return -1;
  return 1 + Math.max(height(node.left), height(node.right));
}

// Total node count
function countNodes(node) {
  if (node === null) return 0;
  return 1 + countNodes(node.left) + countNodes(node.right);
}

// Leaf node count
function countLeaves(node) {
  if (node === null) return 0;
  if (node.left === null && node.right === null) return 1;
  return countLeaves(node.left) + countLeaves(node.right);
}

// Usage example
const root = new TreeNode('A');
root.left = new TreeNode('B');
root.right = new TreeNode('C');
root.left.left = new TreeNode('D');

console.log('Height:', height(root));
console.log('Total nodes:', countNodes(root));
console.log('Leaf nodes:', countLeaves(root));

Done With the Learning

Mark Binary Tree Properties as done and view it on your dashboard

Explore Other Tree Topics

Binary Tree Types