Member Avatar for dubdub

Is there a simple way to find and store the depth of every node in a BST using recursion? I can't seem to figure out a straightforward way of doing so.

  • 2 Contributors
  • 1 Reply
  • 98 Views
  • 6 Hours Discussion Span
  • Latest Post Latest Post by BestJewSinceJC
Member Avatar for BestJewSinceJC

Well the depth is the length of the path from the root of the tree to the node (the number of edges encountered). A binary tree has two children so you can write a simple method that takes a depth (originally passed in as 0) and a Node (the root is originally passed in). Then at the end of the method you'd increment depth, then call the same method with method (depth, leftChild) and another call to method(depth, rightChild). So that you know what Node has what depth, you could do a variety of things, but assuming you're passing in the root node then traversing with Node.leftChild and Node.rightChild, this shouldn't be a problem anyway. (In other words, why are you having trouble storing it? You could simply have a depth variable in your Node class and eliminate the problem quite simply.)

You could also look into Binary Heaps, if you wikipedia them, the wikipedia page has a section called "Heap implementation" that explains how to represent a binary tree as a heap. If you were to arrange your tree like that, finding the depth then becomes an arithmetic problem I believe.

Edited by BestJewSinceJC because: n/a
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.