Pages

Friday, July 19, 2013

Printing Outside Nodes (Boundary) Of A Binary Tree

Contrary to many solutions I found online for this problem - I'm going to say a breadth first search (while printing the first and the last element) is not appropriate here and it won't help in cases where the tree has leafs at levels closer to the root, and those algorithms would miss that. The solution here is a depth first pre-order algorithm, but let me explain the problem statement first. So having the tree below (it is a binary search tree), print the boundary nodes of the tree anticlockwise. Printing the boundary nodes for our tree should result in the following sequence: [60, 41, 16, 25, 42, 55, 62, 64, 70, 65, 74].

Simple Binary Search Tree
Fig. 1 - Simple Binary Search Tree

A pre-order traversal is more appropriate here because it traverses branches in the way we need; for example, it will traverse [60, 41, 16, 25] first which is what we need and we print them. The next sequences are of no interest to us, so we could add a flag that determines whether nodes should be printed out or not (ex: print only leaf nodes). So out of [53, 46, 42, 55, 74, 65, 63, 62, 64, 70] we would print only leaf nodes [42, 55, 62, 64, 70]. We're left with right branch only, where we have to print all the non-leaf nodes. For this we could have a separate stack where, while traversing we add the non-leaf nodes. In code this may look like this:




10 comments:

  1. If this week’s PGA Championship is anything like the other majors this season, it will be one of the most-watched PGA Championships in recent memory. Much of that can be attributed to the return of Tiger Woods.

    Whether it’s Woods, Rory McIlroy, Jordan Spieth or another reason that has you tuning in for the event, there will be no shortage on places your can view it. As far as online streaming goes, there will be featured group coverage provided by the event and Turner and CBS, which owns the rights to broadcast the tournament. (Look for Woods to be in one of those featured groups. He has been most of the season.)

    Check out the schedule below for all your streaming needs, which can be found on PGA.com and the PGA Championship mobile app. (All times ET.)

    Featured Group No. 1 (a.m. and p.m. groups)
    Thurs / Fri: 8:30 a.m. – 7 p.m.
    Sat / Sun: 11 a.m. – 7 p.m.

    Featured Group No. 2 (a.m. and p.m. groups)
    Thurs / Fri: 9:30 a.m. – 7 p.m.
    Sat / Sun: 11 a.m. – 7 p.m.

    Featured Holes: 16, 17, & 18
    Thurs/Fri: 2 p.m. – 8 p.m.
    Sat/Sun: 11 a.m. – 7 p.m.

    TNT Simulcast
    Thurs/Fri: 2 – 8 p.m.
    Sat/Sun: 11 a.m. – 2 p.m.

    CBS Simulcast
    Sat / Sun: 2 p.m. – 7 p.m.

    PGA Championship
    PGA Championship Live
    PGA Championship Live Stream
    PGA Championship 2018
    PGA Championship Golf

    PGA Championship
    PGA Championship Live
    PGA Championship 2018
    PGA Championship Golf
    2018 PGA Championship

    ReplyDelete
  2. Printing service too can be quantified by the quality put into your prints. Highly-professional looking prints which are consistent and accurate are one of the strongest assets a printing company can have.
    cheap 3d printer

    ReplyDelete