Topic: Binary Tree
Tree
Trees: Unlike Arrays, Linked Lists, Stack and queues, which are linear data
structures, trees are hierarchical data structures.
Tree
Important Terms
Following are the important terms with respect to tree.
Node – Each element in binary tree is known as Node
Path − Path refers to the sequence of nodes along the edges of a tree.
Root − The node at the top of the tree is called root. There is only one root per tree
and one path from the root node to any node.
Parent − Any node except the root node has one edge upward to a node called
parent.
Child − The node below a given node connected by its edge downward is called its
child node.
Leaf − The node which does not have any child node is called the leaf node.
Subtree − Subtree represents the descendants of a node.
Levels − Level of a node represents the generation of a node. If the root node is at
level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.
Why tree?
1. One reason to use trees might be because you want to store
information that naturally forms a hierarchy. For example, the
file system on a computer:
2. Trees (with some ordering e.g., BST) provide moderate
access/search (quicker than Linked List and slower than
arrays).
3. Trees provide moderate insertion/deletion (quicker than
Arrays and slower than Unordered Linked Lists).
4. Like Linked Lists and unlike Arrays, Trees don’t have an upper
limit on number of nodes as nodes are linked using pointers.
Main applications of trees
1. Manipulate hierarchical data.
2. Make information easy to search (see tree
traversal).
3. Manipulate sorted lists of data.
4. As a workflow for compositing digital images for
visual effects.
5. Router algorithms
6. Form of a multi-stage decision-making (see business
chess).
Binary Tree
Binary Tree: A tree whose elements have at most 2 children is
called a binary tree. Since each element in a binary tree can
have only 2 children, we typically name them the left and right
child.
Binary Tree Representation: A tree is represented by a pointer
to the topmost node in tree. If the tree is empty, then value of
root is NULL.
A Tree node contains following parts.
1. Data
2. Pointer to left child
3. Pointer to right child
Conceptual Diagram of Binary Tree
Nodes are added to an ordered binary tree in a specific way:
Start at the root node as the current node.
Repeat
Right subtree
If the data value is greater than the current node's data value, follow the right branch.
If the data value is smaller than the current node's data value, follow the left branch.
Until the current node has no branch to follow.
Add the new node in this position.
Create a Binary Tree
Insertion Operation
The very first insertion creates the tree. Afterwards, whenever an element is to be
inserted, first locate its proper location. Start searching from the root node, then if the
data is less than the key value, search for the empty location in the left subtree and
insert the data. Otherwise, search for the empty location in the right subtree and insert
the data.
Drawing a Binary Tree
Draw a binary search tree by inserting the following numbers from left to
right : 11,6,8,19,4,10,5,17,43,49,31.
Insert a node in a binary tree
FUNCTION INSERT (Value, Root)
EX: 3, 1, 2, 5, 6 IF Root=NULL THEN
Root= New Node (Value)
Return
END IF
IF [Link] > Value THEN
IF [Link] = Null THEN
[Link] = New Node (Value)
Return
END IF
INSERT (Value, [Link])
END IF
IF [Link] < Value THEN
IF [Link] = Null THEN
[Link] = New Node (Value)
Return
END IF
INSERT (Value, [Link])
END IF
END FUNCTION
Add a data item to a binary Tree
Add a data item to a binary Tree
Search a Node in a Binary Tree
FUNCTION Search (Value, Root)
IF Root = Null THEN
PRINT “ The tree is empty. Node not found”
Return Null
END IF
IF [Link]=Value THEN
PRINT “ The Node is found”
Return Root
END IF
IF [Link] > Value THEN
Return Search (Value, [Link])
END IF
IF [Link] < Value THEN
Return Search (Value, [Link])
Search for 2 END IF
Search for 7 END FUNCTION
Create Tree Node class Using Python
class Node:
def __init__(self, data):
[Link] = None
[Link] = None
[Link] = data
def PrintTree(self):
print([Link])
root = Node(10)
[Link]()
Output
10
Python Implementation inserting in to a tree
class Node:
def __init__(self, data): # Print the tree
[Link] = None def PrintTree(self):
[Link] = None if [Link]:
[Link] = data [Link]()
def insert(self, data): print( [Link]),
# Compare the new value with the parent if [Link]:
node [Link]()
if [Link]: # Use the insert method to add
if data < [Link]: nodes
if [Link] is None: root = Node(12)
[Link] = Node(data) [Link](6)
else: [Link](14)
[Link](data) [Link](3)
elif data > [Link]: [Link]()
if [Link] is None:
[Link] = Node(data)
else: Output
[Link](data) 3,6,12,14
else:
[Link] = data
Python Implementation Searching a value from a tree
class Node: # findval method to compare the value
def __init__(self, data): with nodes
def findval(self, lkpval):
[Link] = None
if lkpval < [Link]:
[Link] = None
[Link] = data if [Link] is None:
# Insert method to create nodes return str(lkpval)+" Not Found"
def insert(self, data): return [Link](lkpval)
if [Link]: elif lkpval > [Link]: root = Node(12)
if data < [Link]: if [Link] is None: [Link](6)
if [Link] is None: [Link](14)
return str(lkpval)+" Not Found" [Link](3)
[Link] = Node(data) return [Link](lkpval) print([Link](7))
else: print([Link](14))
[Link](data)
else:
elif data > [Link]: print(str([Link]) + ' is found')
# Print the tree Output
if [Link] is None:
def PrintTree(self): 7 Not Found
[Link] = Node(data)
else: if [Link]: 14 is found
[Link](data) [Link]()
else: print( [Link]),
[Link] = data
if [Link]:
[Link]()