Check If Given Undirected Graph is a tree

Objective: Given an undirected graph, Write an algorithm to determine whether its tree or not. An undirected graph is a tree if it has properties mentioned below There is no cycle present in the graph. The graph is connected. (All the vertices in the graph are connected) Example: Recommended articles to read before continue reading … Read more Check If Given Undirected Graph is a tree

Check the completeness of given binary tree | Set 2 – Using Level Order Traversal

Objective: Given a binary tree, write an algorithm to determine whether the tree is complete or not using Level order traversal. Earlier we had solved this problem by counting the number of nodes in the tree. (Read – Check the completeness of given binary tree | Set 1 – Using Node Count. In this article, … Read more Check the completeness of given binary tree | Set 2 – Using Level Order Traversal

Check the completeness of given binary tree | Set 1 – Using Node Count

Objective: Given a binary tree, write an algorithm to determine whether the tree is complete or not.  Complete Binary Tree: A binary tree T with n levels is complete if all levels except possibly the last are completely full, and the last level has all its nodes to the left side. Example:  Below is an … Read more Check the completeness of given binary tree | Set 1 – Using Node Count

Check if the given binary tree is Full or not.

Objective: Given a binary tree, write an algorithm to check if the tree is Full or not. Full binary tree:  A binary tree T is full if each node is either a leaf or possesses exactly two child nodes. See the example below Approach: Do postorder traversal. Check if the node is a leaf node … Read more Check if the given binary tree is Full or not.

Count the number of nodes in a given binary tree

Objective: Given a binary tree, write an algorithm to count all the nodes in the tree. Example: Approach: Do postorder traversal. If the root is null return 0. (base case all well for the recursion) if the root is not null then make a recursive call to the left child and right child and add … Read more Count the number of nodes in a given binary tree

Convert Binary Tree into Threaded Binary Tree

Objective: Given a binary tree write an algorithm to convert it into threaded binary tree. Note: Tree node has extra Boolean field to be used. In earlier article “Introduction to Threaded Binary Tree” we have seen what is threaded binary tree, types of it and what advantages it has over normal binary tree. In this … Read more Convert Binary Tree into Threaded Binary Tree

Double Threaded Binary Tree Complete Implementation

In earlier article “Introduction to Threaded Binary Tree” we have seen what is threaded binary tree, types of it and what advantages it has over normal binary tree. In this article we will see the complete implementation of double threaded binary tree. ( Click here to read about “single threaded binary tree“) Image Source : http://web.eecs.umich.edu/~akamil/teaching/su02/080802.ppt … Read more Double Threaded Binary Tree Complete Implementation

Single Threaded Binary Tree Complete Implementation

In earlier article “Introduction to Threaded Binary Tree” we have seen what is threaded binary tree, types of it and what advantages it has over normal binary tree. In this article we will see the complete implementation of single threaded binary tree.( Click here to read about “double threaded binary tree”) Image Source : http://web.eecs.umich.edu/~akamil/teaching/su02/080802.ppt Single Threaded: … Read more Single Threaded Binary Tree Complete Implementation

Introduction to Threaded Binary Tree

What is Threaded Binary Tree?? A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers that would normally be null point to the inorder predecessor of the node.    We have the pointers reference the next … Read more Introduction to Threaded Binary Tree

Convert BST to Greater Sum Tree

Objective: Given a binary search tree (BST), convert it into greater sum tree. What is greater sum tree: Greater sum tree is a tree in which every node contains the sum of all the nodes which are greater than the node.  see the example below   Approach: Naive approach will be for every node, traverse … Read more Convert BST to Greater Sum Tree

Generate Maximum revenue by selling K tickets from N windows

Objective: Given ‘N’ windows where each window contains certain number of tickets at each window. Price of a ticket is equal to number of tickets remaining at that window. Write an algorithm to sell ‘k’ tickets from these windows in such a manner so that it generates the maximum revenue. This problem was asked in … Read more Generate Maximum revenue by selling K tickets from N windows

Get the Sum of all left leaves in a Binary tree

Objective: Given a binary tree, find the sum of all the nodes which are left as well as leaves nodes. Example:     Approach: Approach is quite simple. Do the inorder traversal check if node if the left child and leaf node. If yes then add it to the sum. See the code for more … Read more Get the Sum of all left leaves in a Binary tree

Convert binary tree to its Sum tree

Objective: Given a binary tree, write an algorithm to convert it into its Sum tree. What is Sum tree: Sum tree of a binary tree, is a tree where each node in the converted tree will contains the sum of the left and right sub trees in the original tree. Example:   Approach: Recursively calculate … Read more Convert binary tree to its Sum tree

Binary Tree-Postorder Traversal – Non Recursive Approach

Objective: Given a binary tree, write a non recursive or iterative algorithm for postorder traversal. Example: Earlier we have seen “What is postorder traversal and recursive algorithm for it“, In this article we will solve it with iterative/Non Recursive manner. Approach: We have seen how we do inorder and preorder traversals without recursion using Stack, … Read more Binary Tree-Postorder Traversal – Non Recursive Approach

Binary Tree – Preorder Traversal – Non Recursive Approach

Objective: Given a binary tree, write a non recursive or iterative algorithm for preorder traversal. Example: Earlier we have seen “What is preorder traversal and recursive algorithm for it“, In this article we will solve it with iterative/Non Recursive manner. Since we are not using recursion, we will use the Stack to store the traversal, … Read more Binary Tree – Preorder Traversal – Non Recursive Approach