Convert Binary Search Tree (BST) to Sorted Doubly-Linked List

Here is the link which has the implementation in C lang. In this post, i have took the complete content from this link and converted into Java structures.
http://leetcode.com/2010/11/convert-binary-search-tree-bst-to.html

Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.

If the problem statement is still not clear to you, below is a pictorial representation of what you need to do:

i) an ordered binary tree (BST) storing numbers from 1 – 5.

ii) original tree converted to a sorted circular doubly-linked list. Its left and right pointers were modified to point to its previous and next node.

I originally read this interesting problem here: The Great Tree-List Recursion Problem.

Hint:
Think of in-order traversal. How do you ensure that the last element’s right pointer points back to the first element?

A circular doubly-linked list. Think of the left and right pointers in a tree as synonymous to the previous and next pointers in a list.

Solution: 
When I first see this problem, my first thought was in-order traversal. Couldn’t we modify the nodes’ left and right pointers as we do an in-order traversal of the tree? However, we have to beware not to modify the pointers and accessing it at a later time.

As we traverse the tree in-order, we could safely modify a node’s left pointer to point to the previously traversed node as we never use it once we reach a node. We would also need to modify the previously traversed node’s right pointer to point to the current node. Note: The previously traversed node meant here is not its parent node. It is the node’s previous smaller element.

Easy approach, right? But wait, we are still missing two more steps. First, we did not assign the list’s head pointer. Second, the last element’s right pointer does not point to the first element (similar to the first element’s left pointer).

How do we solve this? My approach is pretty easy: Just update the current node’s right pointer to point back to the head and the head’s left pointer to point to current node in each recursive call. As the recursion ends, the list’s head and tail would be automagically updated with the correct pointers. Don’t forget to check for this special case: A list with only one element should have its left and right pointers both pointing back to itself.

A double-linked list with a length of one.

Do you think this approach works? I bet it did! The run time complexity for this solution is O(N) since we are essentially doing a modified in-order traversal. It does have some extra assignments in each recursive call though. But overall I am quite satisfied with this approach because it is intuitive and easy to follow. Besides, we are adapting an existing algorithm (in-order traversal) to solve this problem, isn’t this just neat?

I have converted  C code to Java code from above program.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

// This is a modified in-order traversal adapted to this problem. // prev (init to NULL) is used to keep track of previously traversed node. // head pointer is updated with the list's head as recursion ends. void treeToDoublyList(Node current, Node prev, Node head) {   if (current== null) return;   treeToDoublyList(current.left, prev, head);   // current node's left points to previous node   current.left = prev;   if (prev != null)     prev.right = current;  // previous node's right points to current node   else     head = current; // current node (smallest element) is head of               // the list if previous node is not available   // as soon as the recursion ends, the head's left pointer   // points to the last node, and the last node's right pointer   // points to the head pointer. //To avoid loosing current.right Node right = current.right;   head.left = current; //circular double linked list. head.left points to tail node.   current.right = head; //circular double linked list. tail node right points to head.   // updates previous node   prev = node;   treeToDoublyList(right, prev, head); } // Given an ordered binary tree, returns a sorted circular // doubly-linked list. The conversion is done in-place. Node treeToDoublyList(Node root) {   Node prev = NULL;   Node head = NULL;   treeToDoublyList(root, prev, head);   return head; }

Tree problems

http://crackprogramming.blogspot.in/2013/02/convert-binary-search-tree-to-double.html
http://cslibrary.stanford.edu/109/TreeListRecursion.html
http://leetcode.com/2010/11/convert-binary-search-tree-bst-to.html

Convert Binary tree into double linked list

http://www.geeksforgeeks.org/convert-a-given-binary-tree-to-doubly-linked-list-set-2/

Lowest common ancestor

http://en.wikipedia.org/wiki/Lowest_common_ancestor
http://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-search-tree/

Given values of two nodes in a Binary Search Tree, write a c program to find the Lowest CommonAncestor (LCA). You may assume that both the values exist in the tree.

The function prototype should be as follows:

 BSTNode lca(BSTNode root, int n1, int n2)
 n1 and n2 are two given values in the tree with given root.

For example, consider the BST in diagram, LCA of 10 and 14 is 12 and LCA of 8 and 14 is 8.

Following is definition of LCA from Wikipedia:
Let T be a rooted tree. The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in T that has both n1 and n2 as descendants (where we allow a node to be a descendant of itself).

The LCA of n1 and n2 in T is the shared ancestor of n1 and n2 that is located farthest from the root. Computation of lowest common ancestors may be useful, for instance, as part of a procedure for determining the distance between pairs of nodes in a tree: the distance from n1 to n2 can be computed as the distance from the root to n1, plus the distance from the root to n2, minus twice the distance from the root to their lowest common ancestor. (Source Wiki)

Solutions:
If we are given a BST where every node has parent pointer, then LCA can be easily determined by traversing up using parent pointer and printing the first intersecting node.

We can solve this problem using BST properties. We can recursively traverse the BST from root. The main idea of the solution is, while traversing from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 or same as one of the n1 or n2, is LCA of n1 and n2 (assuming that n1 < n2). So just recursively traverse the BST in, if node's value is greater than both n1 and n2 then our LCA lies in left side of the node, if it's is smaller than both n1 and n2, then LCA lies on right side. Otherwise root is LCA (assuming that both n1 and n2 are present in BST)

LCA of 10 and 14 is 12
LCA of 14 and 8 is 8
LCA of 10 and 22 is 20

Time complexity of above solution is O(h) where h is height of tree. Also, the above solution requires O(h) extra space in function call stack for recursive function calls. We can avoid extra space using iterative solution.

/* Function to find LCA of n1 and n2. The function assumes that both    n1 and n2 are present in BST */ BSTNode lca(BSTNode root, int n1, int n2) {     while (root != NULL)     {          // If both n1 and n2 are less than root, then LCA lies in left         if (root->data > n1 && root->data > n2)            root = root->left;           // If both n1 and n2 are greater than root, then LCA lies in right         else if (root->data < n1 && root->data < n2)            root = root->right;           else break; //example: 14 and 8=> 8     }     return root; }

Creating mirror image of a Binary Tree

Creating a exact mirror image of binary tree

public void reverseTree(BinaryTree node) {
     if (node != null) {
     
//recursively call left and right elements
        reverseTree(node.left);
        reverseTree(node.right);

      //swap the elements
        BinaryTree temp = node.right;
        node.right = node.left;
        node.left = temp;      

   
     }
}

Time complexity: O(n)
Space complexity: O(n)