Showing posts with label Binary Tree. Show all posts
Showing posts with label Binary Tree. Show all posts

Saturday, November 3, 2012

Binary Tree: Inorder Predecessor


Write an algorithm to find the ‘previous’ node (e.g., in-order predecessor) of a given node in a binary search tree where each node has a link to its parent.


To Find the inorder predecessor of node u:
If u has a left child, l, then pred(u) is the rightmost descendent of l
Otherwise, pred(u) is the closest ancestor, v, of u (if any) such that u is de-
scended from the right child of v.
If there is no such ancestor, then pred(u) is undefined.



The running time of TREE-SUCCESSOR on a tree of height his O(h), since we either follow a path up the tree or follow a path down the tree. The procedure TREE-PREDECESSOR, which is symmetric to TREE-SUCCESSOR, also runs in time O(h).

Taking the nodes one at a time and applying the rule:
node C: Does not have a left child. Closest ancestor such that node-C is de-
scended from the right child is node-A. Therefore, the predecessor of node-C
is node-A.
node A: Has a left child, node-B. Rightmost descendent of node-B is node-E.
node E: Has a left child, node-F. Rightmost descendent of node-F is node-G.
node G: Does not have a left child. Closest ancestor such that node-G is de-
scended from the right child is node-F.
node F: Does not have a left child. Closest ancestor such that node-F is de-
scended from the right child is node-B.
node B: Has a left child, node-D. Rightmost descendent of node-D is node-D
itself.
node D: Does not have a left child. There is no ancestor such that node-D is
descended from the right child. Therefore, the predecessor of node-D is
undefined.

Friday, November 2, 2012

Binary Tree: level order linked list


Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (eg, if you have a tree with depth D, you’ll have D linked lists).

Approach:
We can do breadth first traversal of the tree keeping track of the levels, and create a linkedlist of all the nodes at any particular level

Input/Output:
iterative inorder:
3 7 9 15 17 21 25
printing level order:
15
7 21
3 9 17 25

Printing linked list at each level:
Level: 0
15
Level: 1
7 21
Level: 2
3 9 17 25

Monday, March 5, 2012

Spiral Level Order of a Binary Tree.


Following is a tree




You need to print
50 
76 17 
9 23 54 
72 19 14 
12 67 


Modified LEVEL order traversal.


Approach:
1. Use 2 stacks S1 and S2.
2. Keep track of levels and push left to right children on S1 and then pop S1 and push right to left children on S2.


Code input/output:
Printing inorder: 
9 12 14 17 19 23 50 54 67 72 76 
Printing spiral level order: 
50 
76 17 
9 23 54 
72 19 14 
12 67 

Sunday, February 26, 2012

Min depth of a binary tree.


Given a binary tree, compute min depth of a leaf node.


Hint:
1. BFS
2. Recursive implementation
Which is better in time complexity?


BFS has the better complexity.
Recursive implementation has to see all the paths in the tree, the number of paths from root would be 2^d where d is the max depth of the tree.
BFS has to see only 2^d where d is the min depth of the tree.


Code input/output:
Tree values (BST):
int [] A = {12, 9, 15, 4, 10, 13, 20, 14, 25, 30};

Min Depth Recursive: 2
Min Depth BFS: 2
Max Depth: 4


Friday, February 24, 2012

Iterator for Binary Tree.

Implement an iterator for a Binary Tree.



Sunday, February 19, 2012

Print nodes of a BST at a given depth on the same line.


Write code to print out a binary search tree, such that all nodes at a given depth are printed on the same line.






Approach:
This problem is basically asking us to do the breadth First Search of the BST, such that all the nodes at a particular level are printed in new line.


Have a queue data structure.
init by adding root node ie 8 in the queue, then add a marker node which contains "null" elements.
when we dequeue any element from the queue, if its a normal node in the binary search tree then print it and add its not null left & right nodes to queue.
If we get a marker node then print a new line and add it back again to the queue if its not empty.



Code input and output:
int [] A = {8, 3, 10, 1, 6, 14, 4, 7, 13};


Printing inorder recursively: 
1 3 4 6 7 8 10 13 14 
Printing level order traversal of BST: 
8 
3 10 
1 6 14 
4 7 13 

Thursday, December 29, 2011

Count of binary trees, given inorder traversal.


Given an inorder traversal only for a binary tree (not necessarily a BST), give a pseudo code to generate all possible binary trees for this traversal sequence.
Firstly, how many binary trees can be generated given an in-order traversal? I know that given 'n' nodes, number of BTs possible is (2^n)-n. But if we are given a specific in-order sequence, can we cut down on this number?


Strategy: consider that each value could be the root. Recursively find the size of the left and right subtrees.


If you need to build all those Trees, then there are 3 ways a new node N could be added to the already existing set of Tree(s) T to preserve the inorder sequence.
1. N could be added as the rightmost child of tree T.
2. N could be root and T as its left subtree.
3. The right subtree of T say R could be added as left subtree of N and then N added as the right subtree of T.




Sunday, April 10, 2011

Kth Smallest element in Binary Search Tree in O(N) - Recursive and Iterative.

Write a function to take a BST and a value k as input and have it print the kth smallest element in the BST.
Write a function that takes a binary tree as input, and have it perform In order traversal - recursive and then iterative

Output:
97 92 3 10 87 6 46
Printing inorder:
3 6 10 46 87 92 97
K value: 3
Kth Smallest Node Value: 10
Kth Node :10