Construct complete binary tree from preorder traversal list Python

Question

How do I construct a binary tree (not binary search tree) from a preorder listing in Python using only the built in list? Each node in the preorder listing also has a "flag" that shows if it's a leaf or internal node. And each node has 2 children (No 0 or 1 child)

I made a class to represent a Node

class Node:
    def __init__(self, initType):
        self.type = initType
        self.leftChild = None
        self.rightChild = None

I think I should use a stack here, but I don't want to import the stack library.

Solutions I found online are for BST only or the input consists of an inorder list and a preorder list, not just the preorder list alone.

Don't any of the "Related" questions help? FWIW, you can use a standard list as a LIFO stack: use the .append method to push an item onto the list and the .pop method to pop it back off again. — PM 2Ring
– PM 2Ring, Commented Feb 20, 2016 at 6:03
Or you can skip the whole Node class and use index math on your ordered list to get the required node. I.e. root node would be element 0, left child of root 1, right child of root 2, left child of element n - 2*n + 1, right child of element n - 2*n + 2. If the index of child is more than the size of list, then that child does not exist. — Ilya Polenov
– Ilya Polenov, Commented Feb 20, 2016 at 6:07
Preorder here means preorder traversal, not pre-sorted list. — PTN
– PTN, Commented Feb 20, 2016 at 6:25
This type of tree is called a complete binary tree (with two nodes exactly), please edit your question to specify this. — Forge
– Forge, Commented Feb 20, 2016 at 6:37
I agree with PM 2Ring, why not just use list that acts as a LIFO stack? — Jodo1992
– Jodo1992, Commented Feb 20, 2016 at 7:03

Mohammad Sadeq Badakhshanfard · Accepted Answer · 2018-03-02 23:15:16Z

0

You can not uniquely re-create a binary tree given only the pre order traversal. That is why the solutions you found online were for a BST or also provided the in order list as well.

For example, if the pre order list was gives as [1, 2, 3]

then your original binary tree could be:

or it could be:

** notice how they are different trees but would have the same pre order traversal lists!

If this question was asked in an interview, it was meant to see if you would notice the fact that a unique binary tree could not be implemented and have you clarify the question: "Is the binary tree a binary search tree?"

It is very common in interviews to leave out facts from a question to have you ask questions.

answered Mar 2, 2018 at 23:15

Mohammad Sadeq Badakhshanfard

155 bronze badges

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

Collectives™ on Stack Overflow

Construct complete binary tree from preorder traversal list Python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related