# Binary Search Tree - deepest nodes only **URL:** \ **Category:** Factual Questions\ **Created:** [October 13, 2005, 12:55pm UTC](https://boards.straightdope.com/t/binary-search-tree-deepest-nodes-only/326051 "2005-10-13T12:55:30Z")\ **Posts on this page:** 3\ **Page:** 2
**Author:** ![Digital\_Stimulus](https://avatars.discourse-cdn.com/v4/letter/d/aeb1de/32.png) [@Digital\_Stimulus](https://boards.straightdope.com/u/Digital_Stimulus)\ **Post date:** [October 14, 2005, 6:56pm UTC](https://boards.straightdope.com/t/binary-search-tree-deepest-nodes-only/326051/21 "2005-10-14T18:56:27Z")
> [@ExtraKun](#): > > The problem with a DFS is that I need the deepest nodes. In the end, the DFS will give me a queue with the nodes sorted by their height – but how I do know which nodes are the deepest. (They are the last few nodes in the queue, but how many?) You have to maintain the depth at the each node, but that’s not really problem is it? I’d also maintain a “bestdepth” variable (as is done in the recursive solution given), only storing nodes at the current best (and deleting the others when “bestdepth” is incremented). ---
**Author:** ![LSLGuy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lslguy/32/5813_2.png) [@LSLGuy](https://boards.straightdope.com/u/LSLGuy)\ **Post date:** [October 15, 2005, 4:43pm UTC](https://boards.straightdope.com/t/binary-search-tree-deepest-nodes-only/326051/22 "2005-10-15T16:43:04Z")
> [@jawdirk](#): > > Not to be abrasive, but bullshit. Recursion is usually more difficult to comprehend than the non-recursive solution for anyone who didn’t write the code. And for what it’s worth, the non-recursive solution (which always exists btw) has better performance. Yes, you should get comfortable with recursion, but only because pointy headed people who think they are being clever like to write recursive code. For any serious application, you will almost never need recursion. If you find yourself considering a recursive solution, you should think hard about whether there is a reasonably simple non-recursive method. If you can’t think of one, be sure to document your recursive method extensively, because it will likely be difficult for others to understand. Code is much more readable if the input and output to methods can be cleanly encapsulated. With recursion, you’re going to have to understand a bunch of intermediate partial results to understand what’s going on. I think it depends most strongly on your data structure. For an inherently flat structure like an array or list or collection, I agree that a recursive algorithm is almost certainly the result of somebody showing off or screwing around. Conversely, the systems I’m stuck designing & building are rife with trees, the canonical example of a recursive data stucture. Almost every data object we handle is composed of an arbitrary set of generally self-similar sub-objects to an arbitrary breadth & depth. We’re either modelling an org chart of business entities, or of ownership interests, or of personnel superior/subordinate relationships or of parts in assemblies in subassemblies in subassemblies in … Or we’re traversing files in folders in folders in folders or machines in subnets of subnets of subnets of … or of users in LDAP containers in LDAP containers in LDAP containers in or … And a recursive algorithm is ideally suited to traversing, assessing, enumerating, restructuring, maintaining, copying, rendering, etc., those sorts of structures. The equivalent iterative algorithm ends up with lots of variables and/or a stack for internal housekeeping. You can either have the stack be implict in the recursive call chain or you can expose it (and potentially screw it up) by using your own stack. Switching to your idea about keeping a tree membernode count and updating it on node add/delete … That assumes your code controls 100% of the potential changes to the structure. For an academic exercise that’s great. For some business objects that works too. (And, not to be abrasive, it didn’t do what the OP/customer asked for.) But far more often this hunk of code we’re working on right _here_ is reporting on (or acting on) objects it doesn’t control, at least not fully. There may be no provisions in those objects for storing abritrary meta-data and if there is, I need to deconflict my metadata from that which other unrelated (and possibly ignorant or selfish) processes may also be writing to the objects’ metadata store. In the real world of disconnected processes taking place asynchronously on machines halfway across the world (unless the packet gets lost), you can’t generally count on metadata you hope to maintain. What if someody does a backup/restore operation on 1/3rd of your tree without telling you? You end up needing to build a resync tool to reset your metadata. And having a method to detect that your metadata is out of sync with whatever it’s summarizing. And a method to handle that degraded condition gracefully until it’s corrected. Finally, for a tree-shaped structure, it’s almost a sure thing your resync tool will operate by enumerating the tree recursively. Maintaining metadata is, like database normalization, a prime topic for religious flamewars. In an ideal world you’d maintain almost none, just as ideally all your databases would be normalized to the 5th form. Conversely, performance and convenience dictate maintaining some metadata & allowing some denormalization. The same logical problem may have different answers depending on scale and scope. Sometimes Quantity has a Quality all its own. The challenge for professionals is to use their judgement to choose the best mix of purity & practicality to get the job done reliably. ---
**Author:** ![jawdirk](https://avatars.discourse-cdn.com/v4/letter/j/df705f/32.png) [@jawdirk](https://boards.straightdope.com/u/jawdirk)\ **Post date:** [October 15, 2005, 6:19pm UTC](https://boards.straightdope.com/t/binary-search-tree-deepest-nodes-only/326051/23 "2005-10-15T18:19:46Z")
> [@LSLGuy](#): > > I think it depends most strongly on your data structure. For an inherently flat structure like an array or list or collection, I agree that a recursive algorithm is almost certainly the result of somebody showing off or screwing around… Not to be abrasive, but what a fine post! You and **Ultrafilter** made a very clear argument for when recursion is called for, one that I never heard during any of the classes in my M.S. CS. And for what it’s worth, a recursive algorithm seems like the best solution to the OP. Thanks **LSLGuy** , I learned something today! [Previous page](https://boards.straightdope.com/t/binary-search-tree-deepest-nodes-only/326051.md?page=1)