Wednesday, December 17, 2014

Populating Next Right Pointers in Each Node I & II

Updating a solution using Queue, O(n) complexity. Actually, this solution works for both problem...

public class TreeNextPointer {
    public void connect(TreeLinkNode root) {
        if (root == null)
            return;
        Queue q = new LinkedList ();
        q.offer(root);
        while(!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeLinkNode curr = q.poll();
                if(!q.isEmpty() && (i < size - 1))
                    curr.next = q.peek();
                if (curr.left != null)
                    q.offer(curr.left);
                if (curr.right != null)
                    q.offer(curr.right);
            }
        }
    }
}
The first one:
Given a binary tree
    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:
  • You may only use constant extra space.
  • You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
         1
       /  \
      2    3
     / \  / \
    4  5  6  7
After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Nothing but a tree-like linked list traversal.
Set parent = root and nextLevel = parent.left. Using two loops, the outer one goes down each level and the second one assign pointers.



public class TreeNextPointer {
    public void connect(TreeLinkNode root) {
        if (root == null)
            return;
        TreeLinkNode parent = root;
        TreeLinkNode nextLevel = root.left;
        while (parent != null && nextLevel != null)
        {
            TreeLinkNode curr = null;
            //same level
            while (parent != null)
            {
                if (curr == null)
                    curr = parent.left;
                else
                {
                    curr.next = parent.left;
                    curr = curr.next;
                }
                curr.next = parent.right;
                curr = curr.next;
                parent = parent.next;
            }
            parent = nextLevel;
            nextLevel = parent.left;
        }
        
    }
}


The second one:
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
  • You may only use constant extra space.
For example,
Given the following binary tree,
         1
       /  \
      2    3
     / \    \
    4   5    7
After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

Overall it's not hard. However, I had a problem on assigning the nextLevel at the right place.
I did it outside the inner loop at first. Consider a case like this:

  1
 /   \
7    9
     /  \
    1   7
     \     \
      8    10

If I assign the nextLevel outside the inner loop like this:

while (parent != null)
        {
            TreeLinkNode curr = null;
            nextLevel = (parent.left == null) ? parent.right : parent.left;
            while (parent != null)
            {

When it traverse to parent = 7, there will be no nextLevel. And thus 8 will not be assigned the next pointer.

So it should be done in this way:


while (parent != null)
        {
            TreeLinkNode curr = null;
            nextLevel = null;
            while (parent != null)
            {
                if (nextLevel == null)
                     nextLevel = (parent.left == null) ? parent.right : parent.left;


The code:


public class TreeNextPointer {
    public void connect(TreeLinkNode root) {
        if (root == null)
            return;
        TreeLinkNode parent = root;
        TreeLinkNode nextLevel = null;
        while (parent != null)
        {
            TreeLinkNode curr = null;
            nextLevel = null;
            while (parent != null)
            {
                if (nextLevel == null)
                     nextLevel = (parent.left == null) ? parent.right : parent.left;
                if (parent.left != null)
                {
                    if (curr == null)
                        curr = parent.left;
                    else
                    {
                        curr.next = parent.left;
                        curr = curr.next;
                    }
                }
                if (parent.right != null)
                {
                    if (curr == null)
                        curr = parent.right;
                    else
                    {
                        curr.next = parent.right;
                        curr = curr.next;
                    }
                }
                parent = parent.next;
            }
            parent = nextLevel;
        }
        
    }
}

1 comment:

  1. The development of artificial intelligence (AI) has propelled more programming architects, information scientists, and different experts to investigate the plausibility of a vocation in machine learning. Notwithstanding, a few newcomers will in general spotlight a lot on hypothesis and insufficient on commonsense application. IEEE final year projects on machine learning In case you will succeed, you have to begin building machine learning projects in the near future.

    Projects assist you with improving your applied ML skills rapidly while allowing you to investigate an intriguing point. Furthermore, you can include projects into your portfolio, making it simpler to get a vocation, discover cool profession openings, and Final Year Project Centers in Chennai even arrange a more significant compensation.


    Data analytics is the study of dissecting crude data so as to make decisions about that data. Data analytics advances and procedures are generally utilized in business ventures to empower associations to settle on progressively Python Training in Chennai educated business choices. In the present worldwide commercial center, it isn't sufficient to assemble data and do the math; you should realize how to apply that data to genuine situations such that will affect conduct. In the program you will initially gain proficiency with the specialized skills, including R and Python dialects most usually utilized in data analytics programming and usage; Python Training in Chennai at that point center around the commonsense application, in view of genuine business issues in a scope of industry segments, for example, wellbeing, promoting and account.

    ReplyDelete