Tree Terminology and Binary Tree Shapes: Depth, Height, Full vs Complete

One tree, every term on it

A tree is a set of nodes connected by edges in a hierarchy: one node at the top, every other node hanging below exactly one parent, no cycles. That is the whole structure. It is the right shape whenever your data has ancestors and descendants rather than a sequence — file systems, org charts, XML and JSON documents, expression trees, decision trees.

Here is the tree the rest of this section refers to. It is deliberately not binary: the general terms apply to any tree, and using a three-child root keeps you from quietly assuming things that are only true of binary trees.

                 (A)              <- level 1  |  depth 0  |  root
               /  |  \
            (B)  (C)  (D)         <- level 2  |  depth 1
           /  \         \
        (E)   (F)       (G)       <- level 3  |  depth 2
                          \
                          (H)     <- level 4  |  depth 3

Eight nodes, seven edges. That is not a coincidence: a tree with n nodes has exactly n - 1 edges, because every node except the root is reached by exactly one edge from its parent. Count the edges of a drawn tree, add one, and you have the node count — a free consistency check on any tree you have just drawn yourself.

Two entries in that table are the ones people get wrong under time pressure. Leaf is defined by having no children, not by being on the bottom row — C is a leaf even though it sits two levels above H. And degree counts children only, which is not what degree means in graph theory, where it counts every incident edge. Bring the graph definition to a tree question and every internal node's answer is one too high.

Level, depth, height: two of them count down, one counts up

These three are the same idea measured from different ends, and mixing them up is the second-most-common way to lose a mark here.

Depth looks down, height looks up. Depth of a node asks how far did I come from the root; height of a node asks how far can I still fall. They agree at the root — the root's depth is 0 and the root's height is the tree's height — and they are opposites at a leaf: a deep leaf has large depth and height 0.

The depth of the tree (as opposed to a node) is the depth of its deepest leaf, which is the same number as the tree's height. So "depth of the tree" and "height of the tree" are two names for one quantity, while "depth of a node" and "height of a node" are genuinely different. Read which one the question asked for.

Level versus depth is a numbering choice, not a concept. Many sources put the root on level 1; many others put it on level 0, in which case level and depth are the same thing. Where the root is level 1, the relationship is simply:

depth(x) = level(x) - 1

This matters when you plug into a formula. The maximum number of nodes on level L with a level-1 root is 2^(L-1); the maximum number at depth d is 2^d. Same fact, two numberings, and using the level number in the depth formula doubles your answer. When a question numbers the levels on the diagram, use its numbering; when a question says "depth" or "height starts from 0", you are counting edges.

The height clash: edges or nodes, and why your code disagrees with your notes

Now the big one. Two definitions of height are in circulation:

• Height in edges. "The length of the longest path, measured in edges, from the root to a leaf." A leaf has height 0. A single-node tree has height 0. An empty tree is usually given height -1.
• Height in nodes (levels). Count the nodes on that longest path instead. A leaf has height 1. A single-node tree has height 1. An empty tree has height 0.

On any non-empty tree, the node count is exactly one more than the edge count. That is the entire disagreement, and it is why two people who both understand trees perfectly will submit answers that differ by one.

What makes this genuinely dangerous rather than merely annoying is that the standard recursive implementation uses the node convention while the standard written definition uses the edge convention — and they usually appear on the same page. This function:

int height(TreeNode* node) {
    if (node == nullptr) return 0;
    return 1 + max(height(node->left), height(node->right));
}

returns 1 for a single node and 3 for a tree drawn with three rows, because its base case gives the empty tree 0. It is counting levels. If you want the edge count from the same recursion, the base case has to be -1 instead — then the leaf case comes out 1 + max(-1, -1) = 0, which is what the written definition demands.

The program below runs both on one tree so you can see the offset directly. Note the -1 base case in heightInEdges; that single character is the whole difference between the two functions.

How to answer so that neither convention can cost you. State the units. Write height = 2 (edges); 3 if counting levels rather than a bare 2. It takes four seconds, it is not hedging — it is the same information expressed unambiguously — and it is correct under either marking scheme. If the question says "height starts from 0", or defines height as a path length, it means edges. If the question hands you a height() function and asks what it returns, trace the code, not the definition.

// The same tree, two height conventions, answers one apart.
#include <algorithm>
#include <iostream>

struct Node {
    char data;
    Node* left  = nullptr;
    Node* right = nullptr;
    explicit Node(char d) : data(d) {}
};

// Edges: "the longest path, measured in edges, from the root to a leaf".
// A single node has no path at all, so its height is 0, and the empty tree
// must return -1 for the recursion to produce that.
int heightInEdges(const Node* n) {
    if (n == nullptr) return -1;
    return 1 + std::max(heightInEdges(n->left), heightInEdges(n->right));
}

// Nodes: count the levels instead. Empty tree 0, single node 1.
// This is the version most lecture slides print.
int heightInNodes(const Node* n) {
    if (n == nullptr) return 0;
    return 1 + std::max(heightInNodes(n->left), heightInNodes(n->right));
}

int main() {
    Node* root = new Node('A');
    root->left  = new Node('B');
    root->right = new Node('C');
    root->left->left   = new Node('D');
    root->left->right  = new Node('F');
    root->right->left  = new Node('E');
    root->right->right = new Node('G');

    Node solo('X');

    std::cout << "A(B(D,F), C(E,G))  edges=" << heightInEdges(root)
              << "  nodes=" << heightInNodes(root) << "\n";   // edges=2  nodes=3
    std::cout << "single node        edges=" << heightInEdges(&solo)
              << "  nodes=" << heightInNodes(&solo) << "\n";  // edges=0  nodes=1
    std::cout << "empty tree         edges=" << heightInEdges(nullptr)
              << "  nodes=" << heightInNodes(nullptr) << "\n"; // edges=-1 nodes=0

    delete root->left->left;  delete root->left->right;
    delete root->right->left; delete root->right->right;
    delete root->left; delete root->right; delete root;
}

Binary trees, and why left and right are not interchangeable

A binary tree is a tree in which every node has at most two children, and — this is the part that carries weight — the two children are distinguished: one is the left child, one is the right child. The definition is recursive: a binary tree is either empty, or a node with a left subtree and a right subtree, each of which is itself a binary tree. That recursion is why almost every tree function you will write is three lines: handle the empty case, recurse left, recurse right.

Because the two slots are named, these are two different binary trees, not one tree drawn twice:

     A            A
    /              \
   B                B

As unordered trees they are identical — a root with one child. As binary trees they are distinct, they store differently in an array, they print differently under in-order traversal, and in a binary search tree they mean opposite things about B's value. Any answer that treats "has one child" as a complete description of a node is missing half the information.

Two consequences worth keeping:

• A node in a binary tree has degree 0, 1 or 2. A binary tree's tree degree is therefore at most 2.
• Reconstructing a binary tree from traversals needs the in-order sequence. Pre-order plus post-order cannot tell an only-left-child apart from an only-right-child, because it is exactly this left/right distinction that they both fail to record.

Full, perfect, complete: the three shapes, and the word that means two things

This is the vocabulary that shows up in multiple-choice questions, and one of the words is genuinely ambiguous across sources. Learn all three shapes and label them by property rather than by name, and the ambiguity stops mattering.

Perfect. Every level is completely filled, right down to the bottom. All leaves sit at the same depth. A perfect tree of height h (edges) has exactly 2^(h+1) - 1 nodes — 1, 3, 7, 15, 31 — and no other node count is possible.

Perfect: h = 2 (edges), n = 7 = 2^3 - 1
            (A)
          /     \
       (B)       (C)
      /   \     /   \
    (D)   (E) (F)   (G)

Complete. Every level is filled except possibly the last, and the last level is filled from the left with no gaps. The test is mechanical: number the nodes level by level, left to right, starting at 1; the tree is complete exactly when the numbers run 1, 2, 3, ... with nothing skipped. That is the same numbering used to store a tree in an array (left(i) = 2i, right(i) = 2i + 1), which is why completeness is the property heaps care about — a complete tree stores in a flat array with no holes.

Complete but not perfect: n = 6
            (A)
          /     \
       (B)       (C)
      /   \     /
    (D)   (E) (F)          last level fills left to right, no gap

Proper (also called strictly binary). Every node has either 0 or 2 children — no node with a single child. Says nothing about depth: a proper tree can be wildly lopsided as long as no node has exactly one child.

Proper but neither perfect nor complete:
            (A)
          /     \
       (B)       (C)
                /   \
             (D)     (E)
                    /   \
                 (F)     (G)

Now the ambiguity. The word full is used for both of these. Some sources define a full binary tree as one where every level is filled — that is perfect, and those sources are the ones that write "a full binary tree of height h has exactly 2^(h+1) - 1 nodes". Other sources define full as every node having 0 or 2 children — that is proper. Both usages are common; you cannot settle it by being clever. What you can do is notice which definition your question is using, usually from a formula printed nearby: if a node-count formula like 2^(h+1) - 1 appears next to the word, it means perfect.

The containments are worth knowing cold:

• Perfect implies complete, and perfect implies proper.
• Complete does not imply proper: the complete tree above has a node with exactly one child if you add one more node on the left of the last level.
• Proper does not imply complete: the proper tree above has a gap under B.
• Complete does not imply perfect: the six-node tree above is the counterexample.

Balanced, skewed, degenerate: the shapes that decide your complexity

The previous section was about fullness. This one is about lopsidedness, and it is the part that actually affects running time.

Balanced. For every node, the heights of its left and right subtrees differ by at most 1. A balanced tree of n nodes has height O(log n), so any operation that walks one root-to-leaf path — a BST search, insert or delete — is O(log n).

Skewed / degenerate. Every node has at most one child, so the tree is a chain. A right-skewed tree leans entirely right, a left-skewed one entirely left, and both have height n - 1:

  right-skewed          left-skewed
     (A)                    (D)
       \                   /
       (B)              (C)
         \              /
         (C)         (B)
           \         /
           (D)    (A)

A degenerate tree is a linked list wearing tree pointers. Every operation that was going to be O(log n) is now O(n), and you are paying two pointers per node for the privilege. This is not a hypothetical: inserting already-sorted data into an ordinary binary search tree produces exactly this shape. Insert 1, 2, 3, 4, 5 in order and every value goes right, forever. The worst case of an unbalanced BST is not adversarial input — it is tidy input, which is why self-balancing trees (AVL, red-black) exist.

The same contrast shows up in array storage. Storing a tree by the level-order numbering needs an array of length about n + 1 when the tree is complete, but 2^n when it is skewed, because the numbering leaves an exponentially growing hole beside the chain. Array storage is excellent for complete trees and catastrophic for skewed ones; linked storage costs the same either way.

The counting formulas

Everything below assumes height in edges, root at depth 0 — the convention the formulas are written for. If you are working in levels, convert first; do not put a level number into a depth formula.

Three of these deserve a sentence of why, because a remembered formula you cannot re-derive is a formula you will misremember at the wrong moment.

2^d at depth d. Depth 0 holds the root alone. Each node has at most two children, so each level can at most double the one above it: 1, 2, 4, 8. Summing that geometric series from depth 0 to depth h gives 2^(h+1) - 1, which is where the max-nodes formula comes from — it is not a separate fact to memorise.

h + 1 minimum. To reach height h you need h edges below the root, and the cheapest way to buy h edges is a chain of h + 1 nodes. Any extra node is optional.

The two min-height expressions are the same number. floor(log2 n) and ceil(log2(n+1)) - 1 agree for every n >= 1; the second is the more obviously derived form (find the smallest h with 2^(h+1) - 1 >= n), the first is the one people quote. The program below prints the tables and brute-force checks that the two expressions match for the first hundred thousand values of n, which is more reassurance than the algebra gives most people at 11pm.

Worked examples, straight off the table: max nodes when h = 4 is 2^5 - 1 = 31; min nodes when h = 2 is 3; min height for n = 23 is 4 (since h = 3 holds only 15 nodes and h = 4 holds up to 31); max height for n = 7 is 6.

// The counting formulas, and a check that the two min-height expressions agree.
#include <cmath>
#include <iostream>

int maxNodesAtDepth(int d)   { return 1 << d; }              // 2^d
int maxNodesOfHeight(int h)  { return (1 << (h + 1)) - 1; }  // 2^(h+1) - 1
int minNodesOfHeight(int h)  { return h + 1; }               // one chain

// Both of these are "the height of the shallowest binary tree holding n nodes",
// measured in edges. They agree for every n >= 1.
int minHeightCeil(int n) {
    int h = 0;
    while (maxNodesOfHeight(h) < n) ++h;   // smallest h with 2^(h+1)-1 >= n
    return h;
}
int minHeightFloor(int n) {
    return static_cast<int>(std::floor(std::log2(static_cast<double>(n))));
}

int main() {
    std::cout << "d : max nodes at that depth\n";
    for (int d = 0; d <= 4; ++d)
        std::cout << "  " << d << " -> " << maxNodesAtDepth(d) << "\n";

    std::cout << "h : min nodes .. max nodes\n";
    for (int h = 0; h <= 4; ++h)
        std::cout << "  " << h << " -> " << minNodesOfHeight(h)
                  << " .. " << maxNodesOfHeight(h) << "\n";

    std::cout << "n : min height, max height\n";
    for (int n : {1, 2, 3, 7, 8, 23, 100}) {
        std::cout << "  " << n << " -> " << minHeightCeil(n)
                  << ", " << (n - 1) << "\n";
    }

    bool agree = true;
    for (int n = 1; n <= 100000; ++n)
        if (minHeightCeil(n) != minHeightFloor(n)) { agree = false; break; }
    std::cout << "ceil(log2(n+1))-1 == floor(log2 n) for n in [1,100000]? "
              << (agree ? "yes" : "no") << "\n";
}

Measuring a tree in C++

One program that computes everything discussed above: both heights, the depth of a named node, node and leaf counts, and the three shape predicates. Read it as the executable form of the definitions — each function is short precisely because each definition is recursive.

Points worth pausing on:

• heightEdges returns -1 on nullptr so a leaf comes out 0; heightNodes returns 0 so a leaf comes out 1. Same recursion, different base case.
• depthOf searches the whole tree, because in a general binary tree there is no way to know which branch holds the key. In a BST you would compare and descend one side, making it O(h) instead of O(n).
• isPerfect does not walk the shape at all. It measures the height, computes 2^(h+1) - 1, and compares against the node count — the formula is the test.
• isComplete uses the array numbering: give the root index 1 and each child 2i / 2i + 1, then a tree of n nodes is complete exactly when no index exceeds n. A gap anywhere pushes some later index past the count.
• isProper checks that a node's two child pointers are either both null or both non-null; (a == nullptr) != (b == nullptr) is the compact way to say "exactly one of them is null".

The program runs the three trees drawn earlier and prints this:

perfect tree A(B(D,F), C(E,G))
  nodes            = 7
  edges            = 6
  height (edges)   = 2
  height (nodes)   = 3
  leaves           = 4
  proper (0 or 2)  = yes
  perfect          = yes
  complete         = yes
complete-not-perfect A(B(D,E), C(F,_))
  nodes            = 6
  edges            = 5
  height (edges)   = 2
  height (nodes)   = 3
  leaves           = 3
  proper (0 or 2)  = no
  perfect          = no
  complete         = yes
right-skewed A-B-C-D
  nodes            = 4
  edges            = 3
  height (edges)   = 3
  height (nodes)   = 4
  leaves           = 1
  proper (0 or 2)  = no
  perfect          = no
  complete         = no

depths in the perfect tree: A=0 B=1 G=2
height of node B (edges) = 1
height of leaf D (edges) = 0

Notice the skewed tree: four nodes and height 3, versus the perfect tree's seven nodes and height 2. More nodes, shorter tree. That gap is the whole argument for balancing.

// Measuring a binary tree: height, depth, counts, and shape predicates.
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <utility>

struct Node {
    char data;
    Node* left  = nullptr;
    Node* right = nullptr;
    explicit Node(char d) : data(d) {}
};

// Height in EDGES. Empty tree is -1 so that a single node comes out as 0,
// which is what "longest root-to-leaf path, measured in edges" requires.
int heightEdges(const Node* n) {
    if (n == nullptr) return -1;
    return 1 + std::max(heightEdges(n->left), heightEdges(n->right));
}

// Height in NODES (levels). This is the shape most textbooks print, and it is
// exactly heightEdges + 1 on any non-empty tree.
int heightNodes(const Node* n) {
    if (n == nullptr) return 0;
    return 1 + std::max(heightNodes(n->left), heightNodes(n->right));
}

// Depth in edges from the root, or -1 if the key is not in the tree.
int depthOf(const Node* n, char key, int d = 0) {
    if (n == nullptr) return -1;
    if (n->data == key) return d;
    int left = depthOf(n->left, key, d + 1);
    if (left != -1) return left;
    return depthOf(n->right, key, d + 1);
}

int countNodes(const Node* n) {
    if (n == nullptr) return 0;
    return 1 + countNodes(n->left) + countNodes(n->right);
}

int countLeaves(const Node* n) {
    if (n == nullptr) return 0;
    if (n->left == nullptr && n->right == nullptr) return 1;
    return countLeaves(n->left) + countLeaves(n->right);
}

// Proper / strictly binary: every node has either 0 or 2 children.
bool isProper(const Node* n) {
    if (n == nullptr) return true;
    if ((n->left == nullptr) != (n->right == nullptr)) return false;
    return isProper(n->left) && isProper(n->right);
}

// Perfect: every level completely filled. Equivalent to n == 2^(h+1) - 1.
bool isPerfect(const Node* n) {
    int h = heightEdges(n);
    int expected = (1 << (h + 1)) - 1;   // h == -1 gives expected == 0
    return countNodes(n) == expected;
}

// Complete: number the nodes level by level from 1. The tree is complete
// exactly when no index exceeds the node count -- i.e. the array layout has
// no holes.
bool isComplete(const Node* root) {
    if (root == nullptr) return true;
    int n = countNodes(root);
    std::queue<std::pair<const Node*, int>> q;
    q.push({root, 1});
    while (!q.empty()) {
        auto [node, index] = q.front();
        q.pop();
        if (index > n) return false;
        if (node->left)  q.push({node->left,  2 * index});
        if (node->right) q.push({node->right, 2 * index + 1});
    }
    return true;
}

void report(const std::string& name, const Node* root) {
    int n = countNodes(root);
    std::cout << name << "\n"
              << "  nodes            = " << n << "\n"
              << "  edges            = " << (n - 1) << "\n"
              << "  height (edges)   = " << heightEdges(root) << "\n"
              << "  height (nodes)   = " << heightNodes(root) << "\n"
              << "  leaves           = " << countLeaves(root) << "\n"
              << "  proper (0 or 2)  = " << (isProper(root)   ? "yes" : "no") << "\n"
              << "  perfect          = " << (isPerfect(root)  ? "yes" : "no") << "\n"
              << "  complete         = " << (isComplete(root) ? "yes" : "no") << "\n";
}

void destroy(Node* n) {
    if (n == nullptr) return;
    destroy(n->left);
    destroy(n->right);
    delete n;
}

int main() {
    //        A
    //      /   \
    //     B     C
    //    / \   / \
    //   D   F E   G
    Node* perfect = new Node('A');
    perfect->left  = new Node('B');
    perfect->right = new Node('C');
    perfect->left->left   = new Node('D');
    perfect->left->right  = new Node('F');
    perfect->right->left  = new Node('E');
    perfect->right->right = new Node('G');

    //        A
    //      /   \
    //     B     C
    //    / \   /
    //   D   E F
    Node* complete = new Node('A');
    complete->left  = new Node('B');
    complete->right = new Node('C');
    complete->left->left  = new Node('D');
    complete->left->right = new Node('E');
    complete->right->left = new Node('F');

    //   A
    //    \
    //     B
    //      \
    //       C
    //        \
    //         D
    Node* skewed = new Node('A');
    skewed->right = new Node('B');
    skewed->right->right = new Node('C');
    skewed->right->right->right = new Node('D');

    report("perfect tree A(B(D,F), C(E,G))", perfect);
    report("complete-not-perfect A(B(D,E), C(F,_))", complete);
    report("right-skewed A-B-C-D", skewed);

    std::cout << "\ndepths in the perfect tree: "
              << "A=" << depthOf(perfect, 'A')
              << " B=" << depthOf(perfect, 'B')
              << " G=" << depthOf(perfect, 'G') << "\n";
    std::cout << "height of node B (edges) = " << heightEdges(perfect->left) << "\n";
    std::cout << "height of leaf D (edges) = " << heightEdges(perfect->left->left) << "\n";

    destroy(perfect);
    destroy(complete);
    destroy(skewed);
}

The mistakes that actually cost marks

1. Answering a height question without saying which unit. The commonest single loss in this topic. Write 2 (edges), 3 (levels) and move on.
2. Writing height() with return 0 on null and then quoting the edge definition. The code counts levels; the definition counts edges. Pick the base case that matches the answer you are claiming: -1 for edges, 0 for levels.
3. Putting a level number into a depth formula. With the root on level 1, level L holds up to 2^(L-1) nodes, not 2^L. Convert to depth first if you are unsure: depth = level - 1.
4. Using the graph-theory degree. In a tree, degree counts children only. A node with a parent and two children has degree 2, not 3.
5. Confusing degree of a node with degree of the tree. The tree's degree is the maximum over all nodes — one number for the whole tree.
6. Calling a node a leaf because it is on the bottom row, or refusing to call one a leaf because it is not. A leaf is a node with no children, at any depth.
7. Swapping full and complete. Complete means every level filled except possibly the last, which fills from the left. If a source's "full" comes with the formula 2^(h+1) - 1, that source means perfect.
8. Assuming complete implies proper, or proper implies complete. Neither holds. Only perfect implies both.
9. Treating left and right as interchangeable. A left-only child and a right-only child are different trees, and in a BST they are contradictory claims about the value.
10. Forgetting that the tree's depth and the tree's height are the same number while a node's depth and height are not. Read whether the question asks about the tree or about a node.
11. Skipping the null base case in a recursive tree function. if (node == nullptr) return ...; is the first line of essentially every tree function you will write. Without it you dereference null on the first leaf.
12. Believing sorted input is the easy case for a BST. It is the worst case: sorted insertion order produces a fully skewed tree and turns every O(log n) operation into O(n).

Exercises with solutions

Work through each question before opening the solution below it.

                (P)
              /  |  \
           (Q)  (R)  (S)
          /  \        |
       (T)   (U)     (V)
                      |
                     (W)

            (A)
          /     \
       (B)       (C)
      /            \
    (D)             (E)
                      \
                      (F)

int height(Node* n) {
    if (n == nullptr) return 0;
    return 1 + std::max(height(n->left), height(n->right));
}

  T1              T2                 T3
      (A)             (A)                (A)
    /     \         /     \            /     \
  (B)     (C)     (B)     (C)        (B)     (C)
  / \     / \     / \     /          /
(D) (E) (F) (G) (D) (E) (F)        (D)
                                   /
                                 (E)

bool isComplete(const Node* root) {
    if (root == nullptr) return true;
    int n = countNodes(root);
    std::queue<std::pair<const Node*, int>> q;
    q.push({root, 1});
    while (!q.empty()) {
        auto [node, index] = q.front();
        q.pop();
        if (index > n) return false;
        if (node->left)  q.push({node->left,  2 * index});
        if (node->right) q.push({node->right, 2 * index + 1});
    }
    return true;
}

Related pages