Binary Tree
Last updated
A binary tree is a hierarchy where each node has at most two children, called the left and right child. The top node is the root, nodes with no children are leaves, and the number of edges from the root to the deepest leaf is the tree's height. Unlike a binary search tree, a plain binary tree has no ordering rule - it's just the shape. Press play above to watch a tree fill level by level, then get walked in-order (left, node, right).
Binary trees underpin many structures - binary search trees, heaps, expression trees, and more. Traversals visit every node in a defined order: in-order, pre-order, and post-order are the three depth-first walks, each useful for different tasks.
Terminology
| Term | Meaning |
|---|---|
| Root | The top node, with no parent |
| Leaf | A node with no children |
| Height | Longest root-to-leaf path (in edges) |
| Depth | Distance of a node from the root |
| Complete | All levels full except possibly the last, filled left to right |
The three depth-first traversals
| Traversal | Order | Common use |
|---|---|---|
| In-order | Left, node, right | Sorted output of a BST |
| Pre-order | Node, left, right | Copy / serialize a tree |
| Post-order | Left, right, node | Delete / evaluate a tree |
Worked example
In-order traversal of the tree built from [4, 2, 6, 1, 3, 5] (filled level by level):
| Step | At node | Action |
|---|---|---|
| 1 | 4 | Recurse into left subtree of 4 before visiting it |
| 2 | 2 | Recurse into left subtree of 2 before visiting it |
| 3 | 1 | Leaf, no left child - visit 1, output [1] |
| 4 | 2 | Left done - visit 2, output [1, 2], then recurse right |
| 5 | 3 | Leaf - visit 3, output [1, 2, 3] |
| 6 | 4 | Left subtree done - visit 4, output [1, 2, 3, 4], then recurse right |
| 7 | 5 | Left child of 6, a leaf - visit 5, output [1, 2, 3, 4, 5] |
| 8 | 6 | Left done, no right child - visit 6, output [1, 2, 3, 4, 5, 6] |
When to use a binary tree
| Use it when | Avoid it when |
|---|---|
| You need to model inherently hierarchical data (file systems, expression trees, DOM) | The data is flat and a list or array would do - a tree only adds overhead |
| You want ordered operations and can keep it balanced (a BST or self-balancing tree) | You need O(1) average lookup by key - a hash table beats any tree |
| You need in-order, pre-order, or post-order processing of structured data | Nodes are inserted in sorted order into an unbalanced BST - it degrades to an O(n) list |
| Range queries or ordered iteration matter, which hash tables cannot provide | Memory is tight - each node carries two child pointers plus the payload |
Binary Tree code
A clean, runnable Binary Tree implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Binary Tree code in Python
Python
1from collections import deque2
3
4class Node:5 def __init__(self, value):6 self.value = value7 self.left = None8 self.right = None9
10
11def insert(root, value):12 # Level-order insert: fill the first empty child slot found13 if root is None:14 return Node(value)15 queue = deque([root])16 while queue:17 node = queue.popleft()18 if node.left is None:19 node.left = Node(value)20 return root21 queue.append(node.left)22 if node.right is None:23 node.right = Node(value)24 return root25 queue.append(node.right)26
27
28def inorder(node):29 if node is None:30 return []31 return inorder(node.left) + [node.value] + inorder(node.right)32
33
34root = None35for value in [1, 2, 3, 4, 5, 6, 7]:36 root = insert(root, value)37
38print("Root: ", root.value)39print("Inorder:", inorder(root))Binary Tree code in JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.left = null;5 this.right = null;6 }7}8
9class BinaryTree {10 constructor() {11 this.root = null;12 }13
14 // Insert at the first free spot, top to bottom (level order)15 insert(value) {16 const node = new Node(value);17 if (!this.root) {18 this.root = node;19 return;20 }21 const queue = [this.root];22 while (queue.length > 0) {23 const current = queue.shift();24 if (!current.left) {25 current.left = node;26 return;27 }28 if (!current.right) {29 current.right = node;30 return;31 }32 queue.push(current.left, current.right);33 }34 }35
36 inorder(node = this.root, out = []) {37 if (!node) return out;38 this.inorder(node.left, out);39 out.push(node.value);40 this.inorder(node.right, out);41 return out;42 }43}44
45const tree = new BinaryTree();46for (const value of [1, 2, 3, 4, 5, 6, 7]) tree.insert(value);47console.log("Inorder traversal:", tree.inorder().join(" "));Binary Tree code in Java
Java
1import java.util.ArrayDeque;2import java.util.Queue;3
4public class Main {5 static class Node {6 int value;7 Node left, right;8 Node(int value) { this.value = value; }9 }10
11 static Node root;12
13 // Insert at the first free slot in level order (keeps the tree complete)14 static void insert(int value) {15 Node node = new Node(value);16 if (root == null) { root = node; return; }17 Queue<Node> queue = new ArrayDeque<>();18 queue.add(root);19 while (!queue.isEmpty()) {20 Node cur = queue.poll();21 if (cur.left == null) { cur.left = node; return; }22 if (cur.right == null) { cur.right = node; return; }23 queue.add(cur.left);24 queue.add(cur.right);25 }26 }27
28 // Inorder: left subtree, node, right subtree29 static void inorder(Node node, StringBuilder sb) {30 if (node == null) return;31 inorder(node.left, sb);32 sb.append(node.value).append(" ");33 inorder(node.right, sb);34 }35
36 public static void main(String[] args) {37 for (int v = 1; v <= 7; v++) insert(v);38 StringBuilder sb = new StringBuilder();39 inorder(root, sb);40 System.out.println("Root: " + root.value);41 System.out.println("Inorder: " + sb.toString().trim());42 }43}Binary Tree code in C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* left = nullptr;6 Node* right = nullptr;7 explicit Node(int v) : value(v) {}8};9
10Node* insert(Node* root, int value) {11 if (root == nullptr) return new Node(value);12 if (value < root->value) root->left = insert(root->left, value);13 else root->right = insert(root->right, value);14 return root;15}16
17// In-order traversal: left subtree, node, right subtree18void inorder(const Node* node) {19 if (node == nullptr) return;20 inorder(node->left);21 std::cout << node->value << " ";22 inorder(node->right);23}24
25int countNodes(const Node* node) {26 if (node == nullptr) return 0;27 return 1 + countNodes(node->left) + countNodes(node->right);28}29
30int main() {31 Node* root = nullptr;32 for (int value : {8, 3, 10, 1, 6, 14, 4}) {33 root = insert(root, value);34 }35 std::cout << "In-order: ";36 inorder(root);37 std::cout << "\n";38 std::cout << "Node count: " << countNodes(root) << "\n";39 return 0;40}Binary Tree code in C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value;6 struct Node* left;7 struct Node* right;8} Node;9
10Node* newNode(int value) {11 Node* n = malloc(sizeof(Node));12 n->value = value;13 n->left = n->right = NULL;14 return n;15}16
17Node* insert(Node* root, int value) {18 if (root == NULL) return newNode(value);19 if (value < root->value) root->left = insert(root->left, value);20 else root->right = insert(root->right, value);21 return root;22}23
24// In-order traversal: left subtree, node, right subtree25void inorder(const Node* node) {26 if (node == NULL) return;27 inorder(node->left);28 printf("%d ", node->value);29 inorder(node->right);30}31
32int countNodes(const Node* node) {33 if (node == NULL) return 0;34 return 1 + countNodes(node->left) + countNodes(node->right);35}36
37int main(void) {38 int values[] = {8, 3, 10, 1, 6, 14, 4};39 Node* root = NULL;40 for (int i = 0; i < 7; i++) root = insert(root, values[i]);41 printf("In-order: ");42 inorder(root);43 printf("\n");44 printf("Node count: %d\n", countNodes(root));45 return 0;46}Binary Tree FAQ
What is the difference between a binary tree and a binary search tree?
A binary tree simply restricts each node to at most two children, with no ordering. A binary search tree adds the rule that everything in the left subtree is smaller and everything in the right subtree is larger, which is what makes searching fast.
What is an in-order traversal?
In-order traversal visits the left subtree, then the node, then the right subtree, recursively. For a binary search tree this produces the values in sorted ascending order, which is why it's the most common traversal to demonstrate.
What is a complete binary tree?
A complete binary tree has every level fully filled except possibly the last, which is filled from left to right. This shape lets the tree be stored compactly in an array (no child pointers needed), which is how binary heaps are implemented.
When should I use a binary tree instead of an array or hash table?
Reach for a tree when your data is naturally hierarchical or when you need ordered operations like range queries and sorted iteration, which hash tables cannot give you. If you only need fast key lookup with no ordering, a hash table's
O(1) average access beats a tree, and for flat data an array is simpler and more cache-friendly.What is the difference between the height and the depth of a binary tree?
Depth is measured from the root down to a specific node - the number of edges on the path from the root to that node. Height is measured from a node down to its deepest leaf, so the height of the whole tree is the depth of its deepest node. A single-node tree has height
0, and its only node also has depth 0.Why does an unbalanced binary tree perform so badly?
Search, insert, and delete in a binary search tree cost
O(h) where h is the height. When keys are inserted in sorted order the tree becomes a straight line, so h grows to n and every operation degrades to O(n) - no better than a linked list. Self-balancing trees like AVL or red-black trees keep the height at O(log n) to prevent this.Related resources
More visualizations
