Binary tree - Introduction

Data Structure and Algorithms - Tree - Tutorialspoint
  • A tree is called a binary tree if each node has either 0, 1 or 2 children only.
  • It is a family of Data Structures i.e. BST, Heap tree, Syntax tee, Red Black tree, AVL tree etc. all are binary tree.
  • Types of Binary tree:
    • Strict Binary tree - If each node has either 2 children or none.
    • Full Binary tree - If each non leaf node has 2 children and all the leaf nodes are at the same level
    • Complete binary tree - If all the levels are completely filled except possibly the last level and the last level has all the elements as left as possible.

Comments

Post a Comment

Popular posts from this blog

Depth First Search (DFS) - Algorithm - Graph Traversal

Image
"What is Depth First Search (DFS)" DFS is an algorithm for traversing the Graph Data Structure.  We can start from a node and go to one of its neighbours and then its neighbour and so on. After this, we come to the other neighbour of the start node and check its neighbour and so on. Basically, we are traversing in depth. It is similar to the Depth First Traversal of a tree, but unlike a tree, a graph may contain cycles, so we need to keep track of visited nodes too in order to ensure we do not traverse the already traversed node and thus avoid getting stuck in the cycle or loop forever. Algorithm for DFS : [Time Complexity: O(V+E) ,  Space Complexity: O(V+E)] If you want to do DFS recursively : 1. For each node in the node list which are not visited call dfs(current node, visited hashset):          2. If current node is present in visited hashset return           3. Else Print current node and add current node to visited h...
Read more

AVL Tree - Left Rotate and Right Rotate (in LL, RR, LR and RL conditions)

Image
  Hence Algorithm of left rotating a node in AVL tree : treeNode leftRotate(cdn){ treeNode NR = cdn.right; cdn.right = NR.left; // any left child of NR will be right child of cdn NR.left = cdn; / / After doing rotation, we have to adjust the height of cdn and NR now cdn.height = calculateHeight(cdn); NR.height = calculateHeight(NR); // finally we will return newRoot to the recursively calling function return NR; } The algorithm of right rotate is just the mirror image of this : treeNode rightRotate(cdn){ treeNode NR = cdn.left; cdn.left= NR.right; // any right child of NR will be left child of cdn NR.right= cdn; / / After doing rotation, we have to adjust the height of cdn and NR now cdn.height = calculateHeight(cdn); NR.height = calculateHeight(NR); // finally we will return newRoot to the recursive...
Read more

Single Source Shortest Path using BFS - Introduction and Code

Image
  "What is Single Source Shortest Path (SSSP) ?" It is the shortest path from a source node to a destination node / multiple destination nodes. If we use BFS for finding SSSP , we can do this for only unweighted graphs. This is because if we consider a weighted graph for finding SSSP using BFS, the BFS will traverse the graph in a breadth-wise manner. But there might be a path, having less cost that is ignored by BFS. Exception, a case where we can use BFS in a weighted graph too: BFS always has the least number of edges between any two vertices. So if all edges are of the same weight, we can use BFS to find the shortest path. Also. DFS is very inefficient for finding SSSP as we have a tendency to go deep and it might be possible that the target node has been close all this time . The same has been explained here under the heading  "BFS VS DFS - When To Use Which Method ?" Algorithm : It is the same as that of BFS except that here we maintain a parentNode proper...
Read more