CODEWITHSUNDEEP
python-3.xtree
Subhayan Bhattacharya
Subhayan Bhattacharya

Reputation: 5705

How to construct a binary tree from given input

I have to construct a binary tree from some given input. The input comes in below form : . The first line represents the number of lines(n) of data coming next. . The next n lines represents the data in the below form : 1.The first character is the parent node 2. The second character is the child node 3. The third character is the direction.(L represents left child, R represents right child)

A sample input is as follows :

9
1 2 R
1 3 L
2 4 R
2 5 L
3 6 R
3 7 L
5 8 R
5 9 L
7 10 R

Can someone please guide me as to how to write the code for constructing this binary tree. I know this is a very simple question but can someone please guide me as how do i go about this.

I constructed a simple Tree class like this:

class Tree:
    def __init__(self,x):
        self.data = x
        self.left = None
        self.right = None

But i am not able to go ahead with the logic.

Thanks for any answers.

Upvotes: 0

Views: 1010

Answers (1)

Benedikt S. Vogler
Benedikt S. Vogler

Reputation: 564

First you need to understand how a binary tree works and tree traversal. The algorithm works like this:

1. Traverse tree to find parent (first number)
2. If next char is R insert new Tree(secondNumber), else insert Tree at left
3. Repeat

It may be easier to save every added node additionally in a dictionary and do a lookup in the dictionary to instantly find it. This only works if your tree does not contain duplicates. Classical way is to do a tree traversal. Choose any of the linked algorithms above.

Upvotes: 1

Related Questions