Data Structures and Algorithms
TREES
By DEVCOMM
Introduction
A TREE data structure is a hierarchical structure that is used to
represent and organize data in a way that is easy to navigate and
search. It is a collection of nodes that are connected by edges and
has a hierarchical relationship between the nodes.
The topmost node of the tree is called the root, and the nodes below
it are called the child nodes.
REPRESENTATION
Some Terminologies
Parent Node: The node which is a predecessor of a node is called the parent
node of that node. B is the parent node of D, E.
Child Node: The node which is the immediate successor of a node is called
the child node of that node. Examples: D, E are the child nodes of B.
Root Node: The topmost node of a tree or the node which does not have any
parent node is called the root node. A is the root node of the tree.
Leaf Node or External Node: The n odes which do not have any child nodes are
called leaf nodes. K, L, M, N, O, P, G are the leaf nodes of the tree.
Ancestor of a Node: Any predecessor nodes on the path of the root to that node
are called Ancestors of that node. A,B are the ancestor nodes of the node E.
Descendant: Any successor node on the path from the leaf node to that node.
E,I are the descendants of the node B.
Sibling: Children of the same parent node are called siblings. D,E are called
siblings.
Level of a node: The count of edges on the path from the root node to that
node. The root node has level 0.
Internal node: A node with at least one child is called Internal Node.
Neighbour of a Node: Parent or child nodes of that node are called neighbors
of that node.
Subtree: Any node of the tree along with its descendant.
Pop Quiz
Children of 4 -
No. of leaf nodes -
Parent of 6 -
Level of 2 -
Subtrees of 1 and 2 -
Ancestors of 8 -
Tree Traversal Methods
1. Inorder Traversal
2. Preorder Traversal
3. Postorder Traversal
Inorder Traversal
1. Traverse the left subtree
2. Visit the root.
3. Traverse the right subtree
Preorder Traversal
1. Visit the root.
2. Traverse the left subtree
3. Traverse the right subtree
Postorder Traversal
1. Traverse the left subtree
2. Traverse the right subtree
3. Visit the root
Binary Trees
A binary tree is a tree data
structure in which each node can
have at most two children
Basic Operation On Binary Tree:
Inserting an element.
Removing an element.
Searching for an element.
Traversing the tree
Binary Search Tree
A Binary Search Tree (BST) is a
special type of binary tree in which
the left child of a node has a value
less than the node’s value and the
right child has a value greater than
the node’s value. This property is
called the BST property and it makes
it possible to efficiently search,
insert, and delete elements in the
tree.
Properties of BST
Value ( LEFT SUBTREE NODE ) < Value ( ROOT NODE )
Value ( RIGHT SUBTREE NODE ) > Value ( ROOT NODE )
This means everything to the left of the root is less
than the value of the root and everything to the right of
the root is greater than the value of the root. Due to
this performing, a binary search is very easy.
The left and right subtree each must also be a BINARY
SEARCH TREE.
There must be NO DUPLICATE nodes
Question 1 .
WAP to print the preorder traversal
Question 2 .
WAP to get the sum of nodes in a
tree.
