This discussion is archived
6 Replies Latest reply: Oct 5, 2011 4:07 PM by 891631

# N-level tree

Currently Being Moderated
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
Currently Being Moderated
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
Currently Being Moderated
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
Currently Being Moderated
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
Currently Being Moderated
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
Currently Being Moderated
jschell wrote:
``````if (depth >= 3)
throw new Exception("Exceeded depth");``````
Aha! Very Clever!! Nice!!!
• ###### 6. Re: N-level tree
Currently Being Moderated
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

#### Legend

• Correct Answers - 10 points