Data Structure - Binary Tree

 Binary Tree 

Binary Tree is a non-linear and hierarchical data structure where each node has at most two children referred to as the left child and the right child.  The topmost node in a binary tree is called the root, and the bottom-most nodes(having no children) are called leaves.

Representation of Binary Tree

Each node in a Binary Tree has three parts:

·         Data

·         Pointer to the left child

·         Pointer to the right child

 

Terminologies in Binary Tree

·         Parent Node: A node that is the direct ancestor of a node(its child node).

·         Child Node: A node that is the direct descendant of another node (its parent).

·         Ancestors of a node: All nodes on the path from the root to that node (including the node itself).

·         Descendants of a node: All nodes that lie in the subtree rooted at that node (including the node itself).

·         Subtree of a node: A tree consisting of that node as root and all its descendants.

·         Edge: The link/connection between a parent node and its child node.

·         Path in a binary tree: A sequence of nodes connected by edges from one node to another.

·         Leaf Node: In tree,  the bottom-most nodes(having no children) are called leaves.

·         Internal Node: A node that has at least one child.

·         Depth/Level of a Node: The number of edges in the path from root to that node. The depth/level of the root node is zero.

·         Height of a Binary Tree: The number of nodes on the longest path from root to a leaf (max level +1)

Operations On Binary Tree

Following is a list of common operations that can be performed on a binary tree:

1. Traversal: Depth-First Search (DFS) Traversal and Breadth-First Search (BFS) Traversal
2.Search: Search a node in Binary Tree
3. Insertion in a Binary tree and Delete from a Binary Tree

 

Advantages of Binary Tree

·         Efficient Search: Binary Search Trees (a variation of Binary Tree) are efficient when searching for a specific element, as each node has at most two child nodes when compared to linked list and arrays

·         Memory Efficient: Binary trees require lesser memory as compared to other tree data structures, therefore memory-efficient.

·         Binary trees are relatively easy to implement and understand as each node has at most two children, left child and right child.

 

Disadvantages of Binary Tree

·         Limited structure: Binary trees are limited to two child nodes per node, which can limit their usefulness in certain applications. For example, if a tree requires more than two child nodes per node, a different tree structure may be more suitable.

·         Space inefficiency: Binary trees can be space inefficient when compared to other data structures like arrays and linked list. This is because each node requires two child references or pointers, which can be a significant amount of memory overhead for large trees.

 Differences between General Tree and Binary Tree

General Tree

  • ·         General tree has no limit of number of children.
  • ·         Evaluating any expression is hard in general trees.

Binary Tree

  • ·         A binary tree has maximum two children
  • ·         Evaluation of expression is simple in binary tree.

Application of trees

  • ·         Manipulation of arithmetic expression
  • ·         Construction of symbol table
  • ·         Analysis of Syntax
  • ·         Writing Grammar
  • ·         Creation of Expression Tree

 

Tree Traversal

Tree traversal refers to the process of visiting or accessing each node of a tree exactly once in a specific order. Unlike linear data structures such as arrays, linked lists, or queues (which have only one logical way of traversal), trees offer multiple ways to traverse their nodes.

Tree traversals are broadly classified into two categories:


Depth-First Traversal (DFT)

·         Explores as far as possible along a branch before exploring the next branch.

·         Types: Inorder, Preorder, Postorder

Breadth-First Traversal (BFT)

·         Explores nodes level by level from top to bottom.

·         Type: Level Order Traversal.

·         The level order traversal of the above tree is 1, 2, 3, 4, 5, 6, and 7.

Inorder Traversal

Inorder traversal visits the node in the order: Left -> Root -> Right

Algorithm for Inorder Traversal

Inorder(tree )
● Traverse the left subtree, i.e., call Inorder(left->subtree)
● Visit the root.
● Traverse the right subtree, i.e., call Inorder(right->subtree)

Preorder Traversal

Preorder traversal visits the node in the order: Root -> Left -> Right

Algorithm for Preorder Traversal

Preorder(tree)

● Visit the root.
● Traverse the left subtree, i.e., call Preorder(left->subtree)
● Traverse the right subtree, i.e., call Preorder(right->subtree)


Postorder Traversal

Postorder traversal visits the node in the order: Left -> Right -> Root

Algorithm for Postorder Traversal:

Postorder(tree)

●Traverse the left subtree, i.e., call Postorder(left->subtree)
● Traverse the right subtree, i.e., call Postorder(right->subtree)
● Visit the root.


 Level Order Traversal

Level Order Traversal visits all nodes present in the same level completely before visiting the next level.


Binary Search Tree (BST)

A Binary Search Tree (BST) is a special type of binary tree in which:

·         All elements in the left subtree are less than the root node.

·         All elements in the right subtree are greater than the root node.

·         This property is true for every node in the tree.

Properties of BST

1.      Each node has at most two children (left and right).

2.      Left child contains smaller values than the parent node.

3.      Right child contains larger values than the parent node.

4.      Inorder traversal of BST gives elements in sorted order.

5.      No duplicate elements are allowed (in standard BST).

Operations on BST

1. Insertion

·         Start from the root node.

·         Compare the new value with current node.

·         If smaller, move to left subtree.

·         If greater, move to right subtree.

·         Insert the node at the correct empty position.


2. Searching

·         Start from the root.

·         If the value is equal to root, element is found.

·         If smaller, search in left subtree.

·         If greater, search in right subtree.

·         If node becomes NULL, element is not present.

3. Deletion

Deletion of a node in BST is done in three cases:

Case 1: Leaf node
→ Delete the node directly.

Case 2: Node with one child
→ Replace the node with its child.

Case 3: Node with two children
→ Find the inorder successor (smallest node in right subtree).
→ Replace the node value with inorder successor.
→ Delete the inorder successor node.

Tree Traversals in BST

1.      Inorder Traversal (LNR) → Left, Node, Right
→ Gives elements in ascending order

2.      Preorder Traversal (NLR) → Node, Left, Right

3.      Postorder Traversal (LRN) → Left, Right, Node

Applications of BST

1.      Searching and sorting of data.

2.      Used in file systems and databases.

3.      Used to maintain dynamic ordered lists.

4.      Used in compiler syntax trees.

Advantages of BST

1.      Faster searching compared to linear list.

2.      Maintains data in sorted order.

3.      Dynamic size (can grow and shrink).

4.      Efficient insertion and deletion.

Disadvantages of BST

1.      Performance reduces if tree becomes skewed.

2.      Worst case time complexity is high.

3.      Needs extra memory for pointers.

========


AVL Tree

An AVL Tree is a self-balancing Binary Search Tree in which the difference between the heights of the left and right subtrees of any node is at most 1.

This difference is called the Balance Factor.

Balance Factor =  Height of Left Subtree -  Height of Right Subtree

Allowed values of Balance Factor: –1, 0, +1

 

Properties of AVL Tree

1.      It follows all properties of a Binary Search Tree.

2.      It is always height-balanced.

3.      Balance factor of every node is –1, 0, or +1.

4.      It avoids skewed trees.

5.      Searching is faster than normal BST.

Operations in AVL Tree

Insertion

1.      Insert the element as in BST.

2.      Update the height of each node.

3.      Check the balance factor.

4.      If imbalance occurs, perform suitable rotation.

Deletion

1.      Delete the element as in BST.

2.      Update the height of nodes.

3.      Check balance factor.

4.      If imbalance occurs, perform suitable rotation.

Rotations in AVL Tree

To restore balance, rotations are used.

1. LL Rotation (Left-Left)

·         Occurs when insertion is in left subtree of left child.

·         Perform right rotation.

2. RR Rotation (Right-Right)

·         Occurs when insertion is in right subtree of right child.

·         Perform left rotation.

3. LR Rotation (Left-Right)

·         Occurs when insertion is in right subtree of left child.

·         Perform left rotation on left child, then right rotation on root.

4. RL Rotation (Right-Left)

·         Occurs when insertion is in left subtree of right child.

·         Perform right rotation on right child, then left rotation on root.

Traversal in AVL Tree

Same as BST:

·         Inorder

·         Preorder

·         Postorder

Inorder traversal gives sorted order.

Applications of AVL Tree

1.      Database indexing.

2.      Searching and sorting applications.

3.      Memory management.

4.      File systems.

5.      Symbol tables.

Advantages

1.      Always balanced.

2.      Faster search compared to BST.

3.      Guaranteed O(log n) time.

4.      Avoids skewed tree.

Disadvantages

1.      More rotations (extra work).

2.      Complex to implement.

3.      Extra memory for height storage.

Difference between BST and AVL Tree

BST

AVL Tree

May become skewed

Always balanced

Search may be O(n)

Always O(log n)

No rotations

Uses rotations

Simple

Complex

 



Comments

Post a Comment

Popular posts from this blog

PYTHON PROGRAMMING (23UCSCC01) – UNIT - III

Image
  PYTHON PROGRAMMING ( 23UCSCC01 ) – UNIT - III Functions: Function Definition – Function Call – Variable Scope and its Lifetime- Return Statement. Function Arguments : Required Arguments, Keyword Arguments, Default Arguments and Variable Length Arguments- Recursion. Python Strings: String operations- Immutable Strings - Built-in String Methods and Functions - String Comparison. Modules : import statement- The Python module – dir() function – Modules and Namespace – Defining our own modules.   What is a Function in Python? A function is a block of reusable code that performs a specific task. It helps us organize code into small, manageable parts, avoid repetition, and improve clarity. Benefits of Using Functions: ·          Modularity:  Breaking down complex problems into smaller, manageable parts. ·          Reusability:  Avoiding repetitive code by defining a task once an...
Read more

Data Structure - Lab

  1.a. List Abstract Data Type (ADT) using an array   Aim To write a Python program to implement the List Abstract Data Type (ADT) using an array , and to perform basic operations such as insertion, deletion, searching, and display .   Algorithm Start the program. Create an empty list L. Display the menu with list operations. Read the user’s choice. If choice is Insert , read the element and add it to the list. If choice is Delete , read the element and remove it from the list if it exists. If choice is Search , check whether the element is present in the list. If choice is Display , print all the elements of the list. Repeat steps 3–8 until the user selects Exit . Stop the program. # List ADT using Array   L = []    # empty list (array)   while True:     print("\nLIST ADT MENU")     print("1. Insert")     print("2. Delete") ...
Read more

Data Structure

Image
  Data Structure Stack   A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. That means the last element inserted is the first one to be removed.   Characteristics Linear data structure Follows LIFO order Supports insertion and deletion from only one end called the top Efficient for managing recursive function calls, undo operations, etc.   Basic Operations on Stack Operation Description push(x) Inserts an element x on top of the stack pop() Removes the top element of the stack peek() / top() Returns the top element isEmpty() Checks if the stack is empty isFull() Checks if the stack is full (for fixed size array implementation)     Stack Representation Stacks can be implemented in two ways: Using Arrays Using Linked Lists ...
Read more