Node and edge
- Algorithms course
- Intermediate
- Lesson 26/80
- 4 min
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).
Practice 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)).
Starter code
def height(node):
# Compute heightSample 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))Expected output
1
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Edge count
n nodes, ____ edgesn nodes, n - 1 edgesExplanation: n - 1 is right.
2 Node and edge: match the terms
| Term | Meaning |
|---|---|
Level |
Root 0 |
Depth |
Root to node |
Height |
Deepest path |
Empty tree |
-1 |
3 Height of a single-node tree?
- -1
- 1
- 0 Correct answer
- 2
Explanation: 0