Algorithm Series 4
Tree Algorithm Questions
Binary Search Tree Implementation in Java
Binary Heap Implementation
How to insert and delete from a binary search trees?
How to balance an AVL/red-black tree?
Preorder Traversal, No Recursion
void preorderTraversal( Node root ){
Stack stack = new Stack();
stack.push( root );
while( true ){
Node curr = stack.pop();
if( curr == null ) break;
curr.printValue();
Node n = curr.getRight();
if( n != null ) stack.push( n );
n = curr.getLeft();
if( n != null ) stack.push( n );
}
}
1.Cursor <= root
2.While true
{ a.If cursor is not null;
i.push in stack
ii.Cursor <= left child of cursor
b.end
c.If Cursor is NULL
i.Cursor <= top of stack
ii.Pop from stack and print
iii.Cursor <= Right child of cursor
d.end
}
Push the root node to the child stack.
While child stack is not empty
Pop a node from the child stack, and push it to the parent stack.
Push its left child followed by its right child to the child stack.
Now the parent stack would have all the nodes ready to be traversed in post-order.
En-queue right child prior to left child during BFS, and put them into a stack, print the stack after BFS is done.
Check if a tree is balanced?
public static boolean isBalanced(TreeNode root){
return (maxDepth(root) - minDepth(root) <= 1);
}
Check if a tree is binary search tree?
Check whether
all node are
starting
at
valid
range
of
values
allowed
by
the
current
node's
ancestors.
boolean isValid(Node root) {
return isValidHelper(root, Integer.MIN_VALUE,
Integer.MAX_VALUE);
}
boolean isValidHelper(Node curr, int min, int max) {
if (curr.left != null) {
if (curr.left.value < min ||
!isValidHelper(curr.left, min, curr.value))
return false;
}
if (curr.right != null) {
if (curr.right.value > max ||
!isValidHelper(curr.right, curr.value, max))
return false;
}
return true;
}
Is a tree complete? [TODO]
Count number of nodes in the tree if they are less then k returns.
If (no_of_nodes(node->left) == k-1) return node->data
If (no_of_nodes(node->left) >= k) findkthmin(node->left,k)
else findkthmin(node->right, (k - no_of_nodes(node->left) -1))
Count ancestors for each of the nodes, the node whose number of ancestor is 0 is the root.
Set that node to null, and reconstruct ancestor count column and repeat above steps.
Given a sorted (increasing order) array, create a binary tree with minimal height
public static TreeNode addToTree(int arr[], int start, int end){
if (end < start) {
return null;
}
int mid = (start + end) / 2;
TreeNode n = new TreeNode(arr[mid]);
n.left = addToTree(arr, start, mid - 1);
n.right = addToTree(arr, mid + 1, end);
return n;
}
Given a binary search tree, create a linked list of all the nodes at each depth.
Find the next node (eg, in-order successor) of a given node in a binary search tree where each node has a link to its parent
public static TreeNode inorderSucc(TreeNode e) {
if (e != null) {
TreeNode p;
// Found right children -> return 1st inorder node on right
if (e.parent == null || e.right != null) {
p = leftMostChild(e.right);
} else {
// Go up until we’re on left instead of right (case 2b)
while ((p = e.parent) != null) {
if (p.left == e) {
break;
}
e = p;
}
}
return p;
}
return null;
}
Inorder Successor in binary tree without parent pointer
http://tech-queries.blogspot.com/2010/04/inorder-succesor-in-binary-tree-wo.html
The trick is that whenever you go left in searching of that node, make the value of the variable as the value of the parent (I mean from where you go left).
Quasi-Isomorphic trees
Two trees s and t are quasi-isomorphic if s can be transformed into t by swapping left and right children of some of the nodes of s.
The values in the nodes are not important in determining quasi-isomorphism, only the shape is important.
return (quasiisomorphic(treeone->left, treetwo->left)
&& quasiisomorphic(treeone->right, treetwo->right)
|| quasiisomorphic(treeone->right, treetwo->left)
&& quasiisomorphic(treeone->left, treetwo->right));
Isomorphic trees
Two binary trees s and t are isomorphic if they have the same shape; the values stored in the nodes do not affect whether two trees are isomorphic.
return (isomorphic(treeone->left, treetwo->left)
&& isomorphic(treeone->right, treetwo->right));
Print all paths in a binary tree which sum up to that value
On every node, we look "up” to see if we’ve found the sum – bottom-up.
void findSum(TreeNode head, int sum, ArrayList buffer,
int level) {
if (head == null) return;
int tmp = sum;
buffer.add(head.data);
for (int i = level;i >- 1; i--){
tmp -= buffer.get(i);
if (tmp == 0) print(buffer, i, level);
}
ArrayList c1 = (ArrayList) buffer.clone();
ArrayList c2 = (ArrayList) buffer.clone();
findSum(head.left, sum, c1, level + 1);
findSum(head.right, sum, c2, level + 1);
}
Decide if T2 is a subtree of T1 - O(nm)
boolean containsTree(TreeNode t1, TreeNode t2) {
if (t2 == null) return true; // The empty tree is always a subtree
else return subTree(t1, t2);
}
boolean subTree(TreeNode r1, TreeNode r2) {
if (r1 == null)
return false; // big tree empty & subtree still not found.
if (r1.data == r2.data) {
if (matchTree(r1,r2)) return true;
}
return (subTree(r1.left, r2) || subTree(r1.right, r2));
}
boolean matchTree(TreeNode r1, TreeNode r2) {
if (r2 == null && r1 == null)
return true; // nothing left in the subtree
if (r1 == null || r2 == null)
return false; // big tree empty & subtree still not found
if (r1.data != r2.data)
return false; // data doesn’t match
return (matchTree(r1.left, r2.left) &&
matchTree(r1.right, r2.right));
}
}
Find the Lowest common ancestor of two nodes in a binary tree
Solution 1:
If each node has a link to its parent, we could trace p and q’s paths up until they intersect
Solution 2:
Follow a chain in which p and q are on the same side. That is, if p and
q are both on the left of the node, branch left to look for the common ancestor. When p and q are no longer on the same side, you must have found the first common ancestor.
Sub-function: test whether a node is a child of another node - use recursion
Variant:
Find the first common ancestor of two nodes in a binary search tree
Node findLowestCommonAncestor( Node root, Node p1,
Node p2 ){
while( root != null ){
int value = root.getValue();
int value1 = p1.getValue(), value2 = p2.getValue();
if( value > value1 && value > value2 )
{
if(root.getLeft()==p1 || root.getLeft()==p2) return root;
root = root.getLeft();
} else if( value < value1 && value < value2 ){
if(root.getRight()==p1 || root.getRight()==p2) return root;
root = root.getRight();
} else {
return root;
}
}
return null;
}
Find a path between nodes
in
a Binary Tree
The essence is to identify the lowest
common
ancestor.
Huffman code
Always merge 2 least-frequent nodes and re-put it to the priority queue.
Minimum Spanning Tree algorithm
Prim's algorithm
The set A forms a single tree. The safe edge added to A is always a least-weight edge connecting the tree to a vertex not in the tree.
The tree starts from an arbitrary root vertex r.
At each step with an edge that contributes the minimum amount possible to the tree's weight.
Resources
