What a tree is
A tree stores values in nodes. Each node can link down to child nodes. Here every node holds a number and has at most two children, a left one and a right one. A tree like that is a binary tree.
The top node, 50, is the root: the only node with no parent. Nodes with no children, here 20, 40, 60 and 80, are leaves. Computer trees are drawn upside down, with the root at the top.
30 is the parent of 20 and 40, its children. A node's depth counts the links from the root down to it: 50 has depth 0, 30 depth 1, 20 depth 2. The tree's height is its largest depth: 2.
You already use trees. Folders: home holds docs and photos, and docs holds cv.txt. Web pages: the browser reads HTML into a tree of elements, with html at the root and head and body as its children.
Binary search trees
This is a binary search tree. At every node, all values in its left subtree (the child and everything below it) are smaller, and all in its right subtree are larger: 20, 30, 40 are left of 50; 60, 70, 80 right.
Search for 60. Start at the root and compare. 60 is larger than 50, so go right: the whole left side is skipped. 60 is smaller than 70, so go left. Found it, after three comparisons.
Each comparison drops one side, so the choices shrank from 7 to 3 to 1. Every extra level doubles the room: 20 full levels hold over a million values, yet a search needs at most 20 comparisons. This is written O(log n).
Insert and shape
To insert 35, search for it. 35 is smaller than 50: go left. Larger than 30: go right. Smaller than 40: go left. That spot is empty, so 35 becomes a new leaf there. The rule still holds.
Insert 10, 20, 30, 40 in sorted order and each value lands right of the last. The tree becomes a line, so finding 40 checks every node. That is O(n): the work grows with the number of values.
Traversal
A traversal visits every node once. An in-order traversal visits the left subtree, then the node, then the right subtree. On a binary search tree that lists every value in sorted order: 20, 30, 35, 40, 50, 60, 70, 80.
Try it in the Python prompt
;; step 1/10 · Nodes and children >>> class Node: ... def __init__(self, key): ... self.key = key ... self.left = None # left child ... self.right = None # right child ... >>> top = Node(50) >>> top.left = Node(30) >>> top.right = Node(70) >>> top.left.key 30
O(log n), read "order log n", means the work grows like the logarithm of n: doubling the number of values adds about one more comparison. O(n) means the work grows in step with n. A plain binary search tree only stays balanced if the values arrive in a mixed-up order. Self-balancing trees, such as red-black trees and AVL trees, reshape themselves on every insert so the height stays about log2(n).