CMSC 132: Object-Oriented Programming II Trees & Binary Search Trees Department of Computer Science University of Maryland, College Park Trees Trees are hierarchical data structures One-to-many relationship between elements Tree node / element Contains data Referred to by only 1 (parent) node Contains links to any number of (children) nodes Parent node Children nodes Trees Terminology Root ? node with no parent Leaf ? all nodes with no children Interior ? all nodes with children Root node Interior nodes Leaf nodes Trees Terminology Sibling ? node with same parent Descendent ? children nodes & their descendents Subtree ? portion of tree that is a tree by itself ? a node and its descendents Subtree Siblings Trees Terminology Level ? is a measure of a node's distance from root Definition of level If node is the root of the tree, its level is 1 Else, the node's level is 1 + its parent's level Height (depth) ? max level of any node in tree Height = 3 Binary Trees ...