Node and edge

Node, edge, leaf and depth terms.

Node and edge

A tree with n nodes has n-1 edges. Every node except the root connects to exactly one parent; that is why one edge is missing.

Level: the root is level 0, its children level 1, etc. Depth: the number of edges from the root to a node.

Height: the number of edges from the root to the deepest leaf. An empty tree has height -1, a single-node tree 0.

Height computation

The tree height is the longest root-to-leaf path. For an empty tree -1, for a single root 0.

Recursive definition: height(node) = -1 if node is None; otherwise 1 + max(height(left), height(right)).

This derives the tree height from the subtrees' heights. Runs in O(n).

Exercise Tree height

Write height(node). -1 if empty, else 1 + max(left, right). Print 1 with root = Node(1); root.left = Node(2); print(height(root)).

Show example solution

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def height(node):
    # Compute height
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))
root = Node(1)
root.left = Node(2)
print(height(root))

Test yourself

Edge count
```
n nodes, ____ edges
```
Show answer
```
n nodes, n - 1 edges
```
Node and edge: match the terms

Level

Root 0
Depth

Root to node
Height

Deepest path
Empty tree

-1
Height of a single-node tree?
- -1
- 1
- 0
- 2
Show answer

0 — 0

Next lesson: Binary tree

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies