Summary - Trees

Walk a small binary tree and print its values in a mini task.

Summary - Trees

Tree: hierarchical, acyclic; n nodes, n-1 edges. Root, internal, leaf. Binary tree has at most 2 children.

Height: longest path; node count: 1 + left + right. Inorder/preorder/postorder traversals are O(n).

Trees underpin file systems, expression parsing and search (BST).

Exercise Summary: inorder traversal

Write inorder(node). Left-root-right, print values. Print 1 2 3 with root = Node(2); root.left = Node(1); root.right = Node(3); inorder(root).

Show example solution

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def inorder(node):
    # Left-root-right traversal
    if node is None:
        return
    inorder(node.left)
    print(node.val)
    inorder(node.right)
root = Node(2)
root.left = Node(1)
root.right = Node(3)
inorder(root)

Test yourself

Summary - Trees: match the terms

Root

Topmost
Leaf

No children
Height

Longest path
Inorder

Left-root-right

Node-edge

n nodes → ____ edges

Show answer

n nodes → n - 1 edges

What does inorder give on a BST?
- Increasing order
- Random
- Leaves
- Decreasing order
Show answer

Increasing order — Increasing order

Next lesson: BST rule

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies