Trees

Common Terminology

• Node A node is the individual item/data that makes up the data structure
• Root The root is the first/top Node in the tree
• Left Child - The node that is positioned to the left of a root or node
• Right Child - The node that is positioned to the right of a root or node
• Edge The edge in a tree is the link between a parent and child node
• Leaf A leaf is a node that does not contain any children
• Height The height of a tree is determined by the number of edges from the root to the bottommost node

Searching a key

To search a given key in Binary Search Tree, we first compare it with root, if the key is present at root, we return root. If key is greater than root’s key, we recur for right subtree of root node. Otherwise we recur for left subtree.

search, minimum and maximum

can be done fast. If there is no ordering, then we may have to compare every key to search a given key.