6 Replies Latest reply: Oct 5, 2011 6:07 PM by 891631

# N-level tree

Hi,

I have need to create a non-binary tree structure whose max depth needs to be restricted at all times. So, if I needed the depth to be restricted to say 3 and I tried to insert a node
at the leaf that's already at depth=3, it should fail.

Is there an algorithm that works on similar lines? So in my example, the algorithm should basically help me keep the tree at 3 levels at all times.

PJ

Edited by: user3214090 on Mar 9, 2011 1:19 PM
• ###### 1. Re: N-level tree
I do not exactly remember, but, you might want to refer 'red-black' tree. That algorithm maintains a depth of 2 or 3 if I'm not wrong.
• ###### 2. Re: N-level tree
Nope. See Wikipedia for instance.

@OP: why do you need this? It's a very strange requirement. Basically that is going to put an upper bound on the number of nodes you can add to the tree, unless the number of children per parent is infinite, which would make for a degenerate tree that behaves more like a few lists. It seems a pointless restriction.
• ###### 3. Re: N-level tree
Oh! I was in a hurry then and could not verify before posting!! Should have done that. Thanks for the education :)
• ###### 4. Re: N-level tree
user3214090 wrote:
Is there an algorithm that works on similar lines? So in my example, the algorithm should basically help me keep the tree at 3 levels at all times.
``````if (depth >= 3)
throw new Exception("Exceeded depth");``````
• ###### 5. Re: N-level tree
jschell wrote:
``````if (depth >= 3)
throw new Exception("Exceeded depth");``````
Aha! Very Clever!! Nice!!!
• ###### 6. Re: N-level tree
You can create/modify a Union-Find (or Disjoint-set) data structure to fit your needs ( http://en.wikipedia.org/wiki/Disjoint-set_data_structure ).

Edited by: 888628 on 5-ott-2011 16.06