Trees: terminology and representations

A tree is a set of nodes joined by edges so that between any two nodes there is exactly one path. Choose one node as the root and every other node gets a parent: the next node on its path towards the root. The tree then hangs down in levels, like a company’s reporting lines, the folders on a disk or the nested objects of a JSON file. Each node except the root has exactly one edge up to its parent, so a tree of n nodes always has n − 1 edges. This lesson fixes the words you will use for the rest of the module (root, depth, height, leaf, subtree), stores one tree in three different ways in Python and measures what each costs, and then proves the counting facts about binary trees that exam and interview questions rely on, checking each of them on 1,000 random trees.

The words, on one tree

The picture shows the ten departments of an institute. The words below are the ones NIST’s Dictionary of Algorithms and Data Structures uses, and the numbers come from the program further down.

• The root is the one node without a parent: Institute. Every other node has exactly one parent, and the nodes below a node are its children. Engineering, Sciences and Management share a parent, so they are siblings.
• A leaf has no children; there are six here, from Management to Systems Lab. A node with at least one child is an internal node: Institute, Engineering, Sciences and Computer Science.
• Following parents upwards from a node passes through its ancestors; everything below it is its descendants. A node with all its descendants forms a subtree: the subtree of Engineering has five nodes.
• The depth of a node is the number of edges from the root down to it, so the root has depth 0 and AI Lab has depth 3. The nodes at one depth form a level.
• The height of a node is the number of edges on the longest path from it down to a leaf, so every leaf has height 0 and Engineering has height 2. The height of the tree is the height of its root, which is also the largest depth of any node: 3 here.

Depth is measured from the top and height from the bottom. That one sentence settles most confusion between them.

Books disagree about one detail. NIST counts edges, so a tree with a single node has height 0, and it calls the height of an empty tree undefined; programs that use this convention usually return −1 for it. Other books count nodes, so that a single node has height 1 and an empty tree height 0, and some number the levels from 1. Neither is wrong. Every height in this track counts edges, and in an exam or an interview it is worth saying which convention you use before you give a number.

Three ways to store a tree

A program can store the same tree in several shapes, and the best one depends on the questions it has to answer.

A parent array keeps one number per node: parent[i] is the number of node i’s parent, and −1 marks the root. It is the most compact form, it is how trees usually arrive from files and database tables (an employee row with a manager column is a parent array), and it answers “who is my parent?” in O(1). Climbing from a node to the root takes one step per level. What it cannot do quickly is list a node’s children, which needs a scan of the whole array, so programs turn it into child lists in one pass first: children[i] holds the children of node i. The program below does exactly that for the institute, then prints the tree with every node’s depth, height and subtree size, and finds the only path between two departments:

"""An institute's departments stored as a parent array, then printed as an indented tree."""

names = ["Institute", "Engineering", "Sciences", "Management", "Computer Science",
         "Electrical", "Mathematics", "Physics", "AI Lab", "Systems Lab"]
parent = [-1, 0, 0, 0, 1, 1, 2, 2, 4, 4]   # parent[i] is the index of node i's parent; -1 marks the root

# One pass turns "who is my parent" into "who are my children".
children = [[] for _ in parent]
roots = []
for node, p in enumerate(parent):
    if p == -1:
        roots.append(node)
    else:
        children[p].append(node)
assert len(roots) == 1, "a tree has exactly one root"
root = roots[0]


def depth(node):
    """Edges from node up to the root, found by following parent links."""
    d = 0
    while parent[node] != -1:
        node = parent[node]
        d += 1
    return d


def height(node):
    """Edges on the longest downward path from node to a leaf (a leaf has height 0)."""
    return max((1 + height(c) for c in children[node]), default=0)


def size(node):
    """Nodes in the subtree rooted at node, the node itself included."""
    return 1 + sum(size(c) for c in children[node])


def show(node, indent=0):
    label = "  " * indent + names[node]
    print(f"{label:<22} depth {depth(node)}  height {height(node)}  subtree {size(node)}")
    for c in children[node]:
        show(c, indent + 1)


show(root)
leaves = [n for n in range(len(parent)) if not children[n]]
edges = sum(len(c) for c in children)
print(f"{len(parent)} nodes, {edges} edges, {len(leaves)} leaves, {len(parent) - len(leaves)} internal, height {height(root)}")


def path_to_root(node):
    path = [node]
    while parent[node] != -1:
        node = parent[node]
        path.append(node)
    return path


up_from_lab = path_to_root(8)
up_from_physics = path_to_root(7)
print("AI Lab up to the root:", " -> ".join(names[n] for n in up_from_lab))
# The only path between two nodes climbs to the deepest ancestor they share, then goes down.
shared = next(n for n in up_from_lab if n in up_from_physics)
down = up_from_physics[: up_from_physics.index(shared)][::-1]
route = up_from_lab[: up_from_lab.index(shared) + 1] + down
print("AI Lab to Physics:", " -> ".join(names[n] for n in route), f"({len(route) - 1} edges)")

Institute              depth 0  height 3  subtree 10
  Engineering          depth 1  height 2  subtree 5
    Computer Science   depth 2  height 1  subtree 3
      AI Lab           depth 3  height 0  subtree 1
      Systems Lab      depth 3  height 0  subtree 1
    Electrical         depth 2  height 0  subtree 1
  Sciences             depth 1  height 1  subtree 3
    Mathematics        depth 2  height 0  subtree 1
    Physics            depth 2  height 0  subtree 1
  Management           depth 1  height 0  subtree 1
10 nodes, 9 edges, 6 leaves, 4 internal, height 3
AI Lab up to the root: AI Lab -> Computer Science -> Engineering -> Institute
AI Lab to Physics: AI Lab -> Computer Science -> Engineering -> Institute -> Sciences -> Physics (5 edges)

The path from AI Lab to Physics climbs to the deepest ancestor the two nodes share, Institute, and comes down again. Because there is exactly one path between any two nodes, that climb-and-descend route is always the only one there is.

Linked nodes are the third form: each node is an object that holds its value and references to its children. A binary tree’s node has two such references, left and right, and most of the algorithms in this module work on that form, because following a reference is the cheapest way to move down.

Some trees arrive with no root at all. A network of cables, a road map without cycles or a list of family relations is often given as a plain edge list, and every edge is then written into the adjacency lists of both of its ends. A breadth-first walk from any chosen node turns those lists into a parent array, because the node a walk first reaches another node from becomes that node’s parent:

"""Cables between 8 campus buildings, given as an edge list: check that they form a tree, then root it."""
from collections import deque

buildings = ["Server room", "Library", "Hostel A", "Hostel B", "Lab block", "Canteen", "Gym", "Admin"]
cables = [(0, 1), (0, 4), (1, 2), (2, 3), (4, 5), (4, 7), (5, 6)]


def adjacency(n, edges):
    """Each building's list of neighbours: an undirected edge appears in both lists."""
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    return adj


def root_at(adj, root):
    """Breadth-first search from root: the first time a node is reached, the node it was reached from is its parent."""
    parent = [None] * len(adj)
    depth = [None] * len(adj)
    parent[root], depth[root] = -1, 0
    queue = deque([root])
    while queue:
        node = queue.popleft()
        for nxt in adj[node]:
            if depth[nxt] is None:
                parent[nxt], depth[nxt] = node, depth[node] + 1
                queue.append(nxt)
    return parent, depth


def is_tree(n, edges):
    """A graph on n nodes is a tree when it has n - 1 edges and every node is reachable."""
    if len(edges) != n - 1:
        return False
    _, depth = root_at(adjacency(n, edges), 0)
    return all(d is not None for d in depth)


n = len(buildings)
adj = adjacency(n, cables)
print("tree?", is_tree(n, cables), f"({len(cables)} cables for {n} buildings)")
for root in (0, 6):
    parent, depth = root_at(adj, root)
    print(f"rooted at {buildings[root]}: parent = {parent}")
    print(f"  depths = {depth}, height {max(depth)}")
print("tree with one more cable (Hostel B to Gym)?", is_tree(n, cables + [(3, 6)]))
# Seven cables again, but Library to Hostel A moved to Server room to Admin: a loop, and two hostels cut off.
moved = [e for e in cables if e != (1, 2)] + [(0, 7)]
print("tree with that cable moved (Server room to Admin)?", is_tree(n, moved))

tree? True (7 cables for 8 buildings)
rooted at Server room: parent = [-1, 0, 1, 2, 0, 4, 5, 4]
  depths = [0, 1, 2, 3, 1, 2, 3, 2], height 3
rooted at Gym: parent = [4, 0, 1, 2, 5, 6, -1, 4]
  depths = [3, 4, 5, 6, 2, 1, 0, 3], height 6
tree with one more cable (Hostel B to Gym)? False
tree with that cable moved (Server room to Admin)? False

The same eight buildings have height 3 when rooted at the server room and height 6 when rooted at the gym: depth and height belong to a rooted tree, not to the cables. The last two lines show the test for “is this a tree?”. Eight nodes need exactly seven edges and must all be reachable. One more cable creates a loop, and moving one cable leaves seven edges but makes a loop through Admin while Hostel A and Hostel B lose their connection, so neither is a tree.

Each form costs memory differently. Here is one random tree of 100,000 nodes measured in CPython:

"""What the links of a 100,000-node tree cost in CPython, in five representations, measured with tracemalloc."""
import random
import tracemalloc
from array import array

N = 100_000
rng = random.Random(1)
ids = list(range(N))                     # the node numbers exist before any measurement, so none counts them
parents = [-1] + [ids[rng.randrange(i)] for i in range(1, N)]   # node i hangs under a random earlier node


class Node:
    __slots__ = ("key", "children")

    def __init__(self, key):
        self.key = key
        self.children = []


class BinaryNode:
    __slots__ = ("key", "left", "right")

    def __init__(self, key):
        self.key = key
        self.left = self.right = None


def parent_list():
    return list(parents)


def parent_array():
    return array("i", parents)


def child_lists():
    children = [[] for _ in range(N)]
    for node in ids[1:]:
        children[parents[node]].append(node)
    return children


def node_objects():
    nodes = [Node(i) for i in ids]
    for node in ids[1:]:
        nodes[parents[node]].children.append(nodes[node])
    return nodes[0]


def binary_nodes():
    """A complete binary tree of N nodes: node i's children are 2i + 1 and 2i + 2."""
    nodes = [BinaryNode(i) for i in ids]
    for i in ids[1:]:
        p = nodes[(i - 1) // 2]
        if i % 2:
            p.left = nodes[i]
        else:
            p.right = nodes[i]
    return nodes[0]


def measure(build):
    tracemalloc.start()
    kept = build()
    used, _ = tracemalloc.get_traced_memory()
    tracemalloc.stop()
    del kept
    return used


rows = [("parent list (list of int)", parent_list), ("parent array (array of 32-bit int)", parent_array),
        ("child lists (a list per node)", child_lists), ("node objects with child lists", node_objects),
        ("binary node objects (key, left, right)", binary_nodes)]
for label, build in rows:
    used = measure(build)
    print(f"{label:<40} {used / 1e6:6.2f} MB  {used / N:6.1f} bytes a node")

parent list (list of int)                  0.80 MB     8.0 bytes a node
parent array (array of 32-bit int)         0.40 MB     4.0 bytes a node
child lists (a list per node)              8.11 MB    81.1 bytes a node
node objects with child lists             12.10 MB   121.0 bytes a node
binary node objects (key, left, right)     5.60 MB    56.0 bytes a node

• Parent array: 4 bytes a node for the links in an array, 8 in a list. It finds a node’s parent in O(1), but listing a node’s children takes a scan of all n entries. It is the usual form of input files and database tables.
• Child lists: about 81 bytes a node. They list a node’s children in O(number of children) but do not store the parent. They suit algorithms that walk down from a parent array.
• Linked nodes: 56 bytes a node for a binary tree, 121 with a list of children. They list children quickly and find the parent only with an extra parent link. Binary trees and search trees use this form.

The gap is large because a Python list or object carries a header of its own, while array("i") stores plain C integers, 4 bytes each in this run. Two more forms are worth knowing by name. The binary tree representation of a tree, as NIST calls it, gives each node a link to its first child and a link to its next sibling, which turns any tree into a binary one. The array layout of a complete binary tree stores no links at all: with positions counted from 0, the children of position i are at 2i + 1 and 2i + 2 and its parent is at (i − 1) // 2. Binary heaps, a later module, are built on that layout.

Binary trees and their shapes

In a binary tree every node has at most two children, and they are told apart as the left and the right child. The side matters: a root with only a left child and a root with only a right child are two different binary trees. Four shapes have names, given here as NIST defines them.

• Full (also called proper): every node has either zero or two children.
• Perfect: every internal node has two children and every leaf has the same depth. A perfect tree of height h holds $2^{h+1} - 1$ nodes.
• Complete: every level except possibly the deepest is completely filled, and the nodes of the deepest level are as far left as possible. This is the shape the array layout needs.
• Degenerate, or skewed: every internal node has exactly one child, so the tree is a single path and its height is n − 1.

Some textbooks call a perfect tree “full” or even “complete”, and NIST’s entries point this out. When a question uses these words, check which meaning it intends.

Counting facts, and why each one holds

These facts follow from counting edges and levels, and a short argument comes with each one.

1. A tree with n nodes has n − 1 edges. Every node except the root has exactly one edge up to its parent, and every edge joins some child to its parent.
2. Each level holds at most twice as many nodes as the level above it. So depth d holds at most $2^d$ nodes, a tree of height h at most $1 + 2 + \dots + 2^h = 2^{h+1} - 1$, and the other way round, a binary tree with n nodes has height at least floor(log2 n). That smallest height is 9 for 1,000 nodes and 16 for 100,000; the largest, a path, is n − 1.
3. A complete binary tree with n nodes has height exactly floor(log2 n). Its levels 0 to h − 1 are full, which is $2^h - 1$ nodes, and the last level adds between 1 and $2^h$ more, so $2^h \le n < 2^{h+1}$.
4. Leaves are one more than the nodes with two children, in every binary tree. Write n0, n1 and n2 for the numbers of nodes with zero, one and two children. Counting nodes gives n = n0 + n1 + n2, and counting edges gives n − 1 = n1 + 2·n2. Subtract and n0 = n2 + 1. In a full binary tree there are no one-child nodes, so the leaves are exactly one more than the internal nodes, and a full tree always has an odd number of nodes: 50 internal nodes come with 51 leaves, 101 nodes and 100 edges.
5. A binary tree with n nodes has n + 1 empty child places. Its nodes offer 2n places for children and n − 1 of them hold an edge. Those empty places are where new nodes go when a tree grows, and where a written-out tree needs a marker for “nothing here”, as the lesson on serialising trees shows.

The facts, checked on random trees

An argument on paper and a program that counts are two independent checks, and a disagreement between them points at a mistake in one of the two. The program below grows 1,000 random binary trees of up to 200 nodes by putting each new node in a randomly chosen empty place, grows 1,000 random full binary trees, walks every tree with a stack and counts what it finds:

"""Counting facts about binary trees, checked by walking 1,000 random trees of each kind."""
import random

rng = random.Random(7)


def random_binary_tree(n):
    """n nodes; each new node goes into an empty child place chosen at random. Returns left and right lists."""
    left, right = [None] * n, [None] * n
    empty = [(0, "L"), (0, "R")]                 # (parent, side) places a new node can take
    for node in range(1, n):
        p, side = empty.pop(rng.randrange(len(empty)))
        (left if side == "L" else right)[p] = node
        empty += [(node, "L"), (node, "R")]
    return left, right


def random_full_tree(leaves):
    """A full binary tree: start from one leaf, then turn a random leaf into a node with two new leaves."""
    left, right, tips = [None], [None], [0]
    while len(tips) < leaves:
        p = tips.pop(rng.randrange(len(tips)))
        a, b = len(left), len(left) + 1
        left += [None, None]
        right += [None, None]
        left[p], right[p] = a, b
        tips += [a, b]
    return left, right


def census(left, right):
    """Walks the tree from node 0 with a stack and counts what it sees."""
    seen = {"nodes": 0, "edges": 0, "empty": 0, "kids0": 0, "kids1": 0, "kids2": 0, "height": 0}
    stack = [(0, 0)]
    while stack:
        node, depth = stack.pop()
        seen["nodes"] += 1
        seen["height"] = max(seen["height"], depth)
        kids = [c for c in (left[node], right[node]) if c is not None]
        seen["edges"] += len(kids)
        seen["empty"] += 2 - len(kids)
        seen[f"kids{len(kids)}"] += 1
        stack += [(c, depth + 1) for c in kids]
    return seen


broken = {"edges = n - 1": 0, "empty places = n + 1": 0, "leaves = two-child nodes + 1": 0, "height in range": 0}
heights = []
for _ in range(1000):
    n = rng.randint(1, 200)
    s = census(*random_binary_tree(n))
    broken["edges = n - 1"] += s["edges"] != s["nodes"] - 1
    broken["empty places = n + 1"] += s["empty"] != s["nodes"] + 1
    broken["leaves = two-child nodes + 1"] += s["kids0"] != s["kids2"] + 1
    broken["height in range"] += not (s["nodes"].bit_length() - 1 <= s["height"] <= s["nodes"] - 1)
print("1,000 random binary trees of 1 to 200 nodes; trees breaking each fact:")
for fact, count in broken.items():
    print(f"  {fact:<30} {count}")

full_broken = 0
for _ in range(1000):
    s = census(*random_full_tree(rng.randint(1, 100)))
    full_broken += s["kids1"] != 0 or s["kids0"] != (s["kids2"]) + 1
print("1,000 random full binary trees; trees where leaves != internal nodes + 1:", full_broken)

s = census(*random_binary_tree(12))
print(f"one tree that is not full: {s['nodes']} nodes, {s['kids0']} leaves, {s['kids1'] + s['kids2']} internal"
      f" ({s['kids1']} of them with one child), so leaves = internal + 1 fails")

for n in (63,):
    hs = [census(*random_binary_tree(n))["height"] for _ in range(1000)]
    print(f"heights of 1,000 random trees of {n} nodes: lowest {min(hs)}, highest {max(hs)},"
          f" average {sum(hs) / len(hs):.2f} (possible: {n.bit_length() - 1} to {n - 1})")

# A complete tree stored in an array: node i has children 2i + 1 and 2i + 2, so the leftmost path is the deepest.
bad = 0
for n in range(1, 2049):
    h, i = 0, 0
    while 2 * i + 1 < n:
        i, h = 2 * i + 1, h + 1
    bad += h != n.bit_length() - 1
print("complete trees of 1 to 2,048 nodes whose height is not floor(log2 n):", bad)
print("most nodes a binary tree of height h can hold:", ", ".join(f"h={h}: {2 ** (h + 1) - 1}" for h in range(6)))

1,000 random binary trees of 1 to 200 nodes; trees breaking each fact:
  edges = n - 1                  0
  empty places = n + 1           0
  leaves = two-child nodes + 1   0
  height in range                0
1,000 random full binary trees; trees where leaves != internal nodes + 1: 0
one tree that is not full: 12 nodes, 4 leaves, 8 internal (5 of them with one child), so leaves = internal + 1 fails
heights of 1,000 random trees of 63 nodes: lowest 7, highest 16, average 10.59 (possible: 5 to 62)
complete trees of 1 to 2,048 nodes whose height is not floor(log2 n): 0
most nodes a binary tree of height h can hold: h=0: 1, h=1: 3, h=2: 7, h=3: 15, h=4: 31, h=5: 63

No tree broke a fact. The one tree printed on its own shows why the full-tree version needs its condition: with five one-child nodes among its eight internal nodes it has only four leaves, yet four is still one more than its three nodes with two children, as fact 4 says. The heights of random 63-node trees ranged from 7 to 16 with an average of 10.59, far from both the lowest possible height, 5, and the highest, 62. Growing a tree by random empty places produces the same shapes as inserting keys in random order into a binary search tree, which is why such trees stay fairly shallow in practice, and why sorted input, as a later lesson measures, is so much worse.

Exercise: height and leaves from a parent array

The exercise takes a parent array in any order, including a chain of 100,000 nodes, which is deeper than CPython’s default recursion limit of 1,000 calls (sys.getrecursionlimit()). Walking down one level at a time, with a list or a collections.deque of the current level, needs no recursion at all.

def height_and_leaves(parent):
    """parent[i] is the parent of node i, or -1 for the root. Returns (height in edges, number of leaves)."""
    raise NotImplementedError("write height_and_leaves")

from tree_stats import height_and_leaves


def test_single_node():
    """a tree of one node has height 0 and one leaf"""
    assert height_and_leaves([-1]) == (0, 1)


def test_department_tree():
    """the lesson's department tree has height 3 and 6 leaves"""
    assert height_and_leaves([-1, 0, 0, 0, 1, 1, 2, 2, 4, 4]) == (3, 6)


def test_root_is_not_node_zero():
    """node 2 is the root; 0 and 1 are its children, and 3 and 4 hang under 0"""
    assert height_and_leaves([2, 2, -1, 0, 0]) == (2, 3)


def test_star():
    """one root with nine children: height 1, nine leaves"""
    assert height_and_leaves([-1] + [0] * 9) == (1, 9)


def test_long_chain():
    """a chain of 100,000 nodes, each the child of the one before: height 99,999, one leaf"""
    n = 100_000
    assert height_and_leaves([-1] + list(range(n - 1))) == (n - 1, 1)


def test_chain_numbered_upwards():
    """a chain of 50,000 nodes whose numbers grow towards the root: node i's parent is i + 1"""
    n = 50_000
    assert height_and_leaves(list(range(1, n)) + [-1]) == (n - 1, 1)

/** parent[i] is the parent of node i, or -1 for the root. Returns [height in edges, number of leaves]. */
export function heightAndLeaves(parent) {
  throw new Error('write heightAndLeaves');
}

import { test, assert } from 'mysmartcopilot:test';
import { heightAndLeaves } from './tree_stats.mjs';

test('a tree of one node has height 0 and one leaf', () => {
  assert.deepEqual(heightAndLeaves([-1]), [0, 1]);
});

test("the lesson's department tree has height 3 and 6 leaves", () => {
  assert.deepEqual(heightAndLeaves([-1, 0, 0, 0, 1, 1, 2, 2, 4, 4]), [3, 6]);
});

test('node 2 is the root; 0 and 1 are its children, and 3 and 4 hang under 0', () => {
  assert.deepEqual(heightAndLeaves([2, 2, -1, 0, 0]), [2, 3]);
});

test('one root with nine children: height 1, nine leaves', () => {
  assert.deepEqual(heightAndLeaves([-1, 0, 0, 0, 0, 0, 0, 0, 0, 0]), [1, 9]);
});

test('a chain of 100,000 nodes, each the child of the one before: height 99,999, one leaf', () => {
  const n = 100000;
  const parent = Array.from({ length: n }, (_, i) => i - 1);
  assert.deepEqual(heightAndLeaves(parent), [n - 1, 1]);
});

test('a chain of 50,000 nodes whose numbers grow towards the root: node i’s parent is i + 1', () => {
  const n = 50000;
  const parent = Array.from({ length: n }, (_, i) => (i === n - 1 ? -1 : i + 1));
  assert.deepEqual(heightAndLeaves(parent), [n - 1, 1]);
});

Interview questions

Fresher · A tree has 12 nodes. How many edges does it have, and could 12 connected nodes have more edges and still be a tree?

It has 11 edges. Every node except the root has exactly one edge to its parent, and every edge connects a child to its parent, so the edges and the non-root nodes pair up one to one. More edges are impossible. In a connected group of 12 nodes that already has 11 edges, any extra edge joins two nodes that are already connected by a path, and the new edge together with that path forms a cycle. A cycle gives two different routes between the nodes on it, while a tree allows exactly one. So for n nodes, connected with n − 1 edges, acyclic and “exactly one path between any two nodes” all describe the same thing.

Fresher · What is the difference between the depth of a node and its height, and what is the height of a tree with a single node?

Depth looks up and height looks down. A node’s depth is the number of edges between it and the root, so the root has depth 0. Its height is the number of edges on the longest path from it down to a leaf, so every leaf has height 0. The height of a whole tree is its root’s height, which equals the largest depth of any node. A tree with a single node therefore has height 0 when edges are counted, which is the convention of NIST’s dictionary. Some textbooks count nodes instead and give the same tree height 1, so say which convention you are using before you answer a height question.

Key takeaways

• A tree of n nodes has exactly one path between any two nodes and n − 1 edges; a rooted tree gives every node but the root one parent.
• Depth counts edges down from the root, height counts edges down to the deepest leaf, and a single node has height 0 when edges are counted. Always say which convention you use.
• A parent array is compact and answers “parent?” in O(1); child lists and linked nodes answer “children?” quickly and cost far more memory in CPython: 4 bytes a node against 56 to 121 in the run above.
• An edge list describes a tree when it has n − 1 edges and connects every node; a breadth-first walk from any node roots it.
• In every binary tree, leaves are one more than the nodes with two children, and n nodes leave n + 1 empty child places; a complete tree has height floor(log2 n).