CMPT 225 Lecture Notes - Parent Pointer Tree, Binary Search Algorithm, Linked List
Document Summary
Each node is connected by an edge to another node. Can use descendants for children, even if not direct. Don"t call cousins cousins but sometimes look at that relationship. Root can be the leaf, if only one node in tree. Subtree is any node in the tree with all its descendants. How you get from one node to another. Height of a node: length of longest path from that node to leaf. Height of tree = height of root. (length of longest path from root to leaf) Or height of different tree could be number of levels including root. Two definitions differ by one, neither is wrong. Perfect binary tree of height h has 2^(h+1) - 1 nodes, 2^h of which are leaves. Just over half the nodes are leaves (because root has 1) Leaves are all about same distance from the root.