### 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