2

For this tree,

enter image description here

As a beginner, Below is my list representation,

tree = [
          [
              [
                 [
                   [], 3, []
                 ], 
                 10,
                 [
                   [], 17, []
                 ]
              ],
              25,
              [
                 [
                   [], 30, []
                 ],
                 32,
                 [
                   [], 38, []
                 ]
              ]
          ],
          40,
          [
             [
               [], 50, []
             ], 
             78,
             [
               [], 93, []
             ]
          ]
       ]

Is this representation correct using python list?

Can I avoid empty list [] in this representation?

Improve this question
5
  • It is a possible representation. It is not the only possible representation. It is, however, one of the more natural ones. There is nothing wrong with it, nor is there anything wrong with having empty lists. If your tree is not meant to be modified, using always the same empty list would reduce the memory consumption. Commented Jul 17, 2015 at 1:29
  • @Amadan What are the other possible representations? Am still not clear, whether to place empty list, because base case recursion code will be like return type(tree) != list for elements in tree = [], which is empty Commented Jul 17, 2015 at 1:30
  • For an obvious and trivial change, you could have [value, left, right] instead of [left, value, right] - this format would make it trivial to support non-binary trees. You could use None instead of the empty list, even though it would complicate the traversal a bit. You could use custom Node objects or tuples instead. Lots of possibilities. Commented Jul 17, 2015 at 1:35
  • Also, your leaves are nodes with values but no descendants; another representation might have leaves as plain values, and not nodes at all. So instead of [[], 3, []], you'd just have 3. Commented Jul 17, 2015 at 1:37
  • Consider using a single flat list: stackoverflow.com/a/79560414/2429666 Commented Apr 7 at 20:50

3 Answers 3

Reset to default
5

It depends on what you mean by 'represent'. You can represent trees by just having the elements in a list e.g. list = [40,25,78,10,32,50,93,3,17,30,38] Then to iterate through it if you want to recreate the tree you can iterate through the list since you know that the life child of list[(i+1)*2-1] and the right child is list[(i+1)*2].

Note: you have to do i+1 since the first element has index 0, And I is the index of the parent node, e.g. the index+1 of the of 25 is 2 therefore the index+1 of 25's left child is 4.

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

7 Comments

what if it is n-ary tree? Can we follow your representation?
If n is fixed, yes, just replace all 2 with n.
I think you want (i+1)*2 - 1 and (i + 1) * 2. For 0 your method gives 2 and 3, when you want 1 and 2.
I think this is something like doing tree recursion on flattened list.
Yeah (i+1)*2-1 is right, I had the index shifted forward on one my head and forgot to correct it.
|
2

You representation makes a lot of sense since it uses just 2 simple rules. A tree is a list that can be:

[]                          #empty tree
[list, number, list]        #non-empty tree

This simplicity makes it easy to write code for and treat things in an uniform way (and without a lot of if statements).

Another equally simple representation is to use tuples instead of lists and/or use None for empty tree.

Another representation would be to put the numbers in leaf nodes directly in the parent node (e.g. to code the subtree under 10 as [3, 10, 17]). This is more compact and gets rid of empty lists but now the logic is more complex, and a tree could be represented 5 different ways:

[]
[list, number, list]
[list, number, number]
[number, number, list]
[number, number, number]

The representation being more complex means you probably need to write more code.

Improve this answer

1 Comment

i think i should remove empty braces, because it is breaking the definition of leaf node.
0

There are many ways to represent a tree using lists.

You can use a single dimensional list. This works well for full trees with a set number of children. Or for missing children pad the array with None where the child of a leaf node should be. if the current node is at index i, its children will be at index i*2 + 1 and (i+1)*2. your parent will be (i-1)/2.

You could also use the a lisp-like tree representation.

[Root, LEFT_SUB_TREE, RIGHT_SUB_TREE]

you example tree would look like:

[40, [25, [10, 3, 17], [32, 30, 38]], [78, 50, 93]]

leaf nodes don't need to be a list they can just be their value.

This method uses less memory for spare trees than the single dimensional list representation.

It is also easy to make this work for any nary tree as well, with varying number of children per node.

[Root, SUB_TREE_1, SUB_TREE_2, ..., SUB_TREE_n]

Improve this answer

2 Comments

As I said above, my base case is return type(tree) != list
The second representation should work quite well for you then. The children of 10: 3 and 7 are not of type list, same with the children of 32 and 78 (i. e) all leaf nodes are not of type list.

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.