Red Black tree
Posted on January 4, 2012
(Last modified on August 7, 2020)
| 5 minutes
| Kinshuk Chandra
A red-black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically used to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer who called them “symmetric binary B-trees”, but acquired its modern name in a paper in 1978 by Leo J. Guibas and Robert Sedgewick, due to printing press technology of that time. Unfortunately, they were not able to print the paper in red black ink as was supposed, but the name stayed.
[Read More]Iterative or Non recursive Inorder traversal on tree
Posted on January 1, 2012
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
This process when implemented iteratively also requires a stack and a boolean to prevent the execution from traversing any portion of a tree twice. The general process of in-order traversal follows the following steps:
Create an empty stack S. Initialize current node as root Push the current node to S and set current = current->left until current is NULL If current is NULL and stack is not empty then
[Read More]DFS (Depth First Search) on tree or graph
Posted on January 1, 2012
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Consider this tree (which is a graph without a cycle) :
Now DFS means traversing to the depth…and then going up, so here DFS traversal will result in 5 2 -4 3 21 19 25. We can use non recursive as well recursive approach to solve this problem.
A depth first search (DFS) through a tree starts at the root and goes straight down a single branch until a leaf is reached.
[Read More]BFS (Breadth first search ) OR Level Order Traversal on tree
Posted on December 31, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Algorithm
Starting at some arbitrarily chosen vertex s (s stands for start vertex) , we mark v so that we know we’ve visited it, process v, and then visit i.e. mark the vertex as visited and process all of v’s neighbors. Now that we’ve visited and processed all of v’s neighbors, we need to visit and process all of v’s neighbors neighbors Example
So consider the tree:
[Read More]Check if Tree is a Balanced Tree
Posted on December 29, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one
Solution Method 1 - Difference of height at each node should not be greater than 1
Here is the code :
public boolean isBalanced(Node root){ if(root==null){ return true; //tree is empty } else{ int lh = root.
[Read More]Print a Binary Tree in Zig Zag Level Order or spiral order
Posted on December 27, 2011
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Question: Print a binary tree in zig-zag level order. Zig-zag means print 1st level from left to right, then 2nd level right to left and alternate thereafter.
Example: zig-zag level order traversal of below tree will be
0 2 1 3 4 5 6 14 13 12 11 10 9 8 7
Solution1 - Iterative solution
Answer: We usually use a queue for level order traversal of a queue. If we want to use the same here, how will we change direction of traversal on every alternate level?
[Read More]Find Diameter of Binary Tree
Posted on December 23, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
the complexity is O(n^2) . since each node is visi…
Unknown - May 1, 2013
the complexity is O(n^2) . since each node is visit multiple times as the traversal is top bottom and not bottom up.
Find Diameter of Binary Tree
Posted on December 23, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
So this question asks us to find Number of Nodes on the Longest Path in Binary Tree so one thing is sure that this path comprises on two leaves with maximum distance in BT..isn’t it
PS:Don’t confused with finding the maximum distance between two nodes in Binary Tree(as it doesn’t involves 2 leaves)
The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree.
[Read More]Vertical Sum of a Binary Tree
Posted on December 18, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
please explain doubly linked list method in words Anonymous - Apr 6, 2014please explain doubly linked list method in words
Added the basic algo for that:
1. Start with the root node and empty double list listNode
2. Add the value of the rootNode to the current listNode
3. Now whenever you go left, pass listNode.left and root.left and call step1 and 2 recursively.
4. Similarly for right node
Please let me know if I have not explained it properly.
[Read More]Vertical Sum of a Binary Tree
Posted on December 18, 2011
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Question : Find vertical sum of given binary tree.
Example:
1 / \\ 2 3 / \\ / \\ 4 5 6 7 The tree has 5 vertical lines
Vertical-1: nodes-4 => vertical sum is 4
Vertical-2: nodes-2 => vertical sum is 2
Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12
Vertical-4: nodes-3 => vertical sum is 3
Vertical-5: nodes-7 => vertical sum is 7
We need to output: 4 2 12 3 7
[Read More]