Make delicious recipes!

Patterns to remember for Binary Trees


It is clearly difficult to remember so many different ways of solving problems. So we provide a summary of some common ways to solve the above problems. These summarized notes can act like powershots before an exam or an interview. They help to refresh your memory without reading all the questions yet once again.
(Offcourse, you must have practiced or read all the questions almost twice in the past before these powershots start becoming effective).


Whenever solving a problem on Binary Trees, try the following properties:
  1. Traverse the tree in InOrder
    If its a Binary Search Tree, InOrder traversal of the tree will give you a sorted array.
    And sorted arrays are immensely useful. In just O(n), you can:
    1. Remove elements outside a given range
    2. Ascertain whether the given tree is a Binary Search Tree or not
    3. Populate the InOrder successor or predecessor
    4. Find a pair with a given sum
    5. Merge two Binary Search Trees


  2. InOrder traversal without recursion.
    Stack needs to be used so that one can move to the left-most node and then climb back.

  3. PreOrder traversal without recursion.
    This also needs a stack but it's simpler than InOrder, just take care of the order of insertion of left and right in the stack.

  4. PostOrder traversal without recursion.
    This is easy if two points can be remembered:
    • LRD = swapLandR (reverse(DLR))
    • Reverse of a stack can be done by pouring it into another stack.
    So this one needs two stacks but its extremely similar to PreOrder.
    Just put the stuff into second stack where PreOrder prints and you are done.

  5. InOrder traversal without recursion and stack. (Morris Traversal)
    To eliminate the stack, create a thread on the left child's rightmost child.
    This thread will point to the current parent and help in returning back.
    On returning back, nullify the thread again if already present.






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal