Write an algorithm to rotate a node of a binary tree.

Question

Okash · Accepted Answer

To help visualise, right rotation is shown below. Consider a given tree:

                           R
                           /\
                          /  \
                         P  C
                        /\
                       /  \
                      A  B

Imagine nodes as metal coins suspended by strings (branches). For right rotation:
1. Pick up node P and pull it up so that node R falls down to the right of P.
2. Take B (right child of P) and make it left child of node R.

The tree has been right rotated now and looks like this:


                           P
                           /\
                          /  \
                         A  R
                              /\
                             /  \
                            B  C

Similar process can be applied to this tree to rotate it left. This time start by pulling up R above P.

Hope it helps.

avi · Answer

void rotateLeft( Node p) {
        Node r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }


void rotateRight(Node p) {
        Node l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }

Goldman Sachs

Goldman Sachs Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches