Can anyone point out a way of getting the depth of a Node in a Binary Tree (not a balanced one, or BST) without using recursion? Ideally in Java/C/C#
The node is represented as:
class Node
{
Node Left;
Node Right;
string Value;
int Depth;
}
Using Level Order with a FIFO list was my first thought, but I was stumped at detecting when the level changes, particular for unbalanced trees.
I assume you mean filling in the Depth value on node, and/or finding max depth. One way to do this would be using two lists, and doing the level order as suggested. It'd be akin to:
Basically, you enumerate each node on a given level, then find each node on the next level; until you run out of nodes/levels. Clearly, List could be replaced with just about any list like data structure (Linked List, Queue, etc). And the last value of 'level' would be max depth + 1. I suspect.
One other clarification based on re reading of the question; if you are searching for a node with a specific value, and want to find its depth, you would change the foreach loop to include 'if(node.Value==searchValue) return level;'. And, technically, if you are searching for a specific value, you shouldn't be doing a Level Order Traversal, but rather a search for the value using relevant Binary Tree properties (e.g. val < currentNode.Value goto left else goto right), and tracking your depth. If you are given only the Node and want to find its depth, you would either need to perform a binary search for the node from root, or you would need to track the Node's parent.
Here is the most efficient solution I've come up with (C++). The trick is to use a second queue to store the children of all nodes at your current level. This will work for balanced and unbalanced binary trees.
You can implement any resursive method with a stack, which is how resursion works anyways. Imagine your resursive function looks like
The non-resursive function looks something like
EDIT:
This function sets the depth for each node
Here's a simpler solution, I think. If the data structure allowed for an arbitrary number of children, this solution could be easily modified for that case too: