Arrays, linked lists, stacks and queues are used to represent linear and tabular data. These structures are not suitable for representing hierarchical data.
In hierarchical data we have
 ancestors, descendants
 superiors, subordinates, etc
Family Structure
Business Corporate Structure
Federal Government Structure
Introduction to Trees
 Fundamental data storage structures used in programming
 Combine advantages of ordered arrays and linked lists
 Searching can be made as fast as in ordered arrays
 Insertion and deletion as fast as in linked lists
Tree characteristics
 Consists of nodes connected by edges
 Nodes often represent entities (complex objects) such as people, car parts etc.
 Edges between the nodes represent the way the nodes are related.
 It's easy for a program to get from one node to another if there is a line connecting them.
 The only way to get from node to node is to follow a path along the edges.
Tree Terminology
 Root: node without parent (A)
 Internal node: node with at least one child (A, B, C, F)
 External node: (a.k.a. leaf) node without children (E, I, J, K, G, H, D)
 Ancestors of a node: parent, grandparent, grandgrandparent, etc
 Depth of a node: number of ancestors
 Height of a tree: maximum depth of any node (3)
 Descendant of a node: child, grandchild, grandgrandchild, etc
 Degree of an element: no. of children it has
 Subtree: tree consisting of a node and its descendants
 Path: traversal from node to node along the edges that results in a sequence
 Root: node at the top of the tree
 Parent: any node, except root has exactly one edge running upward to another node. The node above it is called parent.
 Child: any node may have one or more lines running downward to other nodes. Nodes below are children.
 Leaf: a node that has no children
 Subtree: any node can be considered to be the root of a subtree, which consists of its children and its children's children and so on.
 Visiting: a node is visited when program control arrives at the node, usually for processing.
 Traversing: to traverse a tree means to visit all the nodes in some specified order.
 Levels: the level of a particular node refers to how many generations the node is from the root. Root is assumed to be level 0.
 Keys: key value is used to search for the item or perform other operations on it.
Binary Trees
 Every node in a binary tree can have at most two children.
 The two children of each node are called the left child and right child corresponding to their positions.
 A node can have only a left child or only a right child or it can have no children at all.

A binary tree is a tree with the following properties:
 Each internal node has at most two children (exactly two for proper binary trees)
 The children of a node are an ordered pair
 We call the children of an internal node left child and right cild

Alternative recursive definition: a binary tree is either
 a tree consisting of a single node, or
 a tree whose root has an ordered pair of children, each of which is a binary tree

Applications:
 arithmetic expressions
 decision processes
 searching
Arithmetic Expression Tree

Binary tree associated with an arithmetic expression
 internal nodes: operators
 external nodes: operands
 Example: arithmetic expression tree for the expression (2 * (a – 1) + (3 * b))
Compiling arithmetic expressions
We can represent an arithmetic expression such as
(A + B) * (C + D) * 2 – X / Y as a binary tree, in which the leaves are constants or variables and the nodes are operations:
Properties of Proper Binary Trees
Notation
 n number of nodes
 e number of external nodes
 i number of internal nodes
 h height
Properties
 e = i +1
 n =2e 1
 h <= i
 h <= (n 1)/2
 e <= 2h
Follow Us!