A tree is a collection of nodes and edges. Edges connects the edges together. In a tree there is one and only one path between any two nodes.
Fig: A tree - here we have A,B,C,D,E,F nodes and l,m,n,o,p, edges.
In a tree we define a path using connected sequence of edges. Number of edges on the path is called the length of the path. In above figure from B to F there is exactly one path and that is (m,n,p).
Rooted tree
In a tree we can pick a node and call it to be the root of the tree. We call this tree to be a rooted tree.
We choose C to be the root and we redraw the tree to keeping the root on top and others in different level based on distance from the root.
Fig1: Original tree Fig2: Redrawn tree
If we look carefully we see that nothing has changed for the tree but we have chosen C to be root and placed the nodes differently on paper. We draw the like figure 2 for convenience of understanding levels and relations.
If we choose any node and find a path from that node to the root the first node we encounter is called the parent of that node. All node except the root has exactly one parent. Root has no parent.
On the path fopm node F to root node C we encounter D first. So D is the parent of F and F is called to be child of D. A node may have any number of children including zero child. A node without any child is called a leaf node. A,F,E are leaf nodes.
All the nodes on the path to root including F itself and the root is called to be ancestor of F. So F's ancestors are F,D and C and F is called to be their descendents.
Length of the path from an node to the root is the depth of that node. Depth of F is 2. Length of path from a node to its deepest descendent is the height of the node. height of D is 1 nad height of root C is 2. Height of the root is also height of the tree. So the tree has a height of 2.
Nodes having same parent is called to be siblings. B and D are siblings. Similarly E and F are siblings.
Binary tree
A binary tree is a special type of three where no node is allowed to have more than two children.
Fig: Binary tree - a node may hav zero, one or two children.
Each child of a node is either left child or a right child. Even there is only one child that child must be either left child or a right chi
Representing rooted tree in memory
----------------------- | data | Parent ref| ----------------------- |Children list | -----------------------
Fig:
----------------------------- | data | Parent ref | ----------------------------- |First child | Next sibling | -----------------------------
Fig:
Traversal
The process of visiting each node in a tree once is called traversal. Depending on the order of visiting nodes in a tree we ma traverse in a few different ways:
- Pre-order traversal
- Post-order traversal
- Binary tree inorder traversal
- Level order traversal
We will discuss them in details.
Preorder traversal
We visit each node starting from root and then recursively visit its children from left to right.
Preorder(node): Visit(node) for each child c of node Preorder(c)
Fig: Preorder traversal - numbers show the order of nodes getting visited
Postorder traversal
We visit each node's children left to right and then visit the node itself.
Preorder(node): for each child c of node Preorder(c) Visit(node)
Fig: Postorder traversal
Binary tree inorder traversal
We visit left child then the node itself and then right chhild.
Inorder(node) if node.left exists Inorder(node.left) Visit(node) if node.right exists Inorder(node.right)
Fig: Inorder traversal
Level order traversal
We visit each level of the tree left to right before visiting any deeper level.
Fig: Level order traversal
We use a queue to keep track of the visited nodes children.
LevelOrder(tree) Q = new empty Queue Q.enque(tree.root) while Q is not empty node = Q.deque() Visit(node) for each child c of node from left to right Q.enqueue(c)
