1

I'm trying to convert a list-based tree implementation into an array-based implementation with the parent at the ith index, left child at 2ith index and right child at 2i+1th index. for some reason the conversion results in loss of data for trees with bigger number of nodes. I'd like to know what all boundary conditions i need to check for while implementing this. Thanks!

Improve this question
3
  • list and array suggest you already have a language in mind. Perhaps you can tag your question with that language? Commented Dec 12, 2012 at 16:40
  • Well, it is simple math if all nodes have the same number of children: root @ 0, L @ 1, R @ 2, LL@3,LR@4,RL@5,RR@6 - so you can see that the pattern - left child is at 2*i + 1, right child at 2*i + 2. If your methods are implemented properly, there is no issue. regarding boundary conditions: you can have at max N generations where sum(2**0...N) <= arrayLength. Commented Dec 12, 2012 at 16:45
  • Only with a "bigger number of nodes"? How big? You're not suffering from some integer overflow, are you? Commented Dec 12, 2012 at 16:57

2 Answers 2

Reset to default
3

Assuming your language uses zero-based indices the children of node i go into 2i + 1 and 2i + 2 not 2i and 2i + 1. The later works for one-based indices.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

Are you putting the head at 0 or 1? Choosing '0' will definitely cause problems, unless you adjust your formula.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.