Static nested class in java

http://stackoverflow.com/questions/253492/static-nested-class-in-java-why

BST problems where the underlying thing happenning is search - whatever be the name of the function

1. Print Ancestors of a given node in Binary Tree - very sweet problem. If the element is on the left subtree or the right subtree from this element, then this element is an ancestor. So, basically its like search on the left and right subtree. Formulate it recursively :    http://www.geeksforgeeks.org/print-ancestors-of-a-given-node-in-binary-tree/
2. LCA of two nodes in a BST : looks complicated. There are few frameworks for all BST problems, traversal or search. Search basically is also a form of traversal only. Just my way of thinking and categorizing.
3. Node *LCA(Node *root, Node *p, Node *q) {

     if (!root) return NULL;

     if (root == p || root == q) return root;

     Node *L = LCA(root->left, p, q);

     Node *R = LCA(root->right, p, q);

     if (L && R) return root;  // if p and q are on both sides

     return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees

   }
4.  
5. sd
6. sd

 

How to get the prev element in an inorder successor in a BST - comparison of two problems

Here think very naively first. You can simply write the inorder traversal of the BST. Now, that would be a sorted array. If two non-adjacent nodes are swapped, then there would be two inflection points in the array. Write a BST, write its inorder traversal and check. Looking at an example you can easily realize that there will be another case where the two adjacent nodes will be swapped. So in that case there will be two inflection points. Now this solution will take O(n) extra space.

However, you can do it easily using recursion. Think about it. First what do you need to think ? How to traverse the tree. Here, you need to compare the previously seen element with the current element. So, if the previous is in the left subtree, the root can be the current. Its a typical case of inorder traversal and is similar to Convert a BST to a double linked list problem.

 We will maintain three pointers, first, middle and last. When we find the first point where current node value is smaller than previous node value, we update the first with the previous node & middle with the current node. When we find the second point where current node value is smaller than previous node value, we update the last with the current node. In case #2, we will never find the second point. So, last pointer will not be updated. After processing, if the last node value is null, then two swapped nodes of BST are adjacent

void correctBSTUtil( struct node* root, struct node** first,

                     struct node** middle, struct node** last,

                     struct node** prev )

{

    if( root )

    {

        // Recur for the left subtree

        correctBSTUtil( root->left, first, middle, last, prev );

 

        // If this node is smaller than the previous node, it's violating

        // the BST rule.

        if (*prev && root->data < (*prev)->data)

        {

            // If this is first violation, mark these two nodes as

            // 'first' and 'middle'

            if ( !*first )

            {

                *first = *prev;

                *middle = root;

            }

 

            // If this is second violation, mark this node as last

            else

                *last = root;

        }

 

        // Mark this node as previous

        *prev = root;

 

        // Recur for the right subtree

        correctBSTUtil( root->right, first, middle, last, prev );

    }

}

 

Look at the way prev is stored here. We just store the root which is the previously seen element. You can get a clear understanding of how this thing can be altered in another problem. Looking at these two problems will improve your clarity of thinking. The problem is Convert a BST to doubly linked list

 

void treeToDoublyList(Node *p, Node *& prev, Node *& head) {

  if (!p) return;

  treeToDoublyList(p->left, prev, head);

  // current node's left points to previous node

  p->left = prev;

  if (prev)

    prev->right = p;  // previous node's right points to current node

  else

    head = p; // current node (smallest element) is head of

              // the list if previous node is not available

              //because prev will come from left subtree in the recursion. There is no left subtree, so it the smallest and head

  // 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.

  Node *right = p->right;

  head->left = p;

  p->right = head;

  // updates previous node

  prev = p; // In an inorder traversal before going to the right subtree the previous always gets updated

  treeToDoublyList(right, prev, head);

}

 

 

// In an inorder traversal before going to the right subtree the previous always gets updated

Trim a given BST based on Min and Max values

How do you think about this problem recursively. First think about the traversals. It cannot be pre order because you have to return the root. So you need the computation of the left subtree and the right subtree done when you return the values. Hence, it has to be post order traversal. Now, since you know the kind of traversal, think of a recursive solution. Suppose you apply your trim function to the left subtree and the right subtree. Now you have the solutions of the left subtree and the right subtree and they satisfy the min and the max criterion. You are now only left to check the min and the max criterion with the root. Now, write down the code.

TreeNode trim(TreeNode node, int min, int max) {
        if(node == null) return node;
        node.left = trim(node.left, min, max);
        node.right = trim(node.right, min, max);
        if(node.data < max and node.data > min) return node;
        else if(node.data < min) return node.right;
        else if(node.data > max) return node.left;


}