Binary Trees: Structure, Node Definition & Types

A binary tree is a tree in which every node has at most two children, conventionally named left and right. That single constraint makes binary trees simple to reason about and is the foundation for binary search trees, heaps, and tries. This page nails down how to represent a node and the standard classification of binary-tree shapes.

The node

Each node stores a value plus two pointers/references to its children. A missing child is null (nullptr / null / None). Here is the canonical TreeNode:

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

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

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

Building a small tree

You wire nodes together by assigning children. This builds the tree 1 with left child 2 and right child 3:

TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
// remember to delete nodes (or use smart pointers) to avoid leaks

TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)

Types of binary trees

Interviewers love these definitions because they sound similar but are precise:

• Full (strict) binary tree: every node has either 0 or 2 children — never exactly one.
• Complete binary tree: every level is completely filled except possibly the last, and the last level fills left to right. Heaps are complete trees.
• Perfect binary tree: every internal node has two children and all leaves sit on the same level. A perfect tree of height h has exactly 2^(h+1) - 1 nodes.
• Balanced binary tree: the heights of the two subtrees of any node differ by at most a small constant, keeping height O(log n) — see balanced trees & AVL.
• Degenerate (skewed) tree: each parent has a single child, so it behaves like a linked list with height O(n).

For beginners: Every perfect tree is complete, and every perfect tree is full — but not the other way around. Draw a few small examples until the distinctions click.

Counting nodes

A quick recursive count demonstrates how naturally recursion fits a binary tree — a node count is 1 + left count + right count:

int countNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

int countNodes(TreeNode root) {
    if (root == null) return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);
}

function countNodes(root) {
  if (root === null) return 0;
  return 1 + countNodes(root.left) + countNodes(root.right);
}

def count_nodes(root):
    if root is None:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

This is O(n) time (it visits every node) and O(h) space for the recursion stack, where h is the tree height.

Complexity at a glance

Going deeper: A complete binary tree can be stored compactly in an array, where node i’s children are at 2i+1 and 2i+2. That trick powers the binary heap.

Next steps

Now learn to visit every node with tree traversals (DFS) and level-order traversal (BFS).