How to construct a binary tree from given input

Question

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 :

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.

Benedikt S. Vogler · Accepted Answer · 2017-09-04 13:12:33Z

1

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.

edited Sep 4, 2017 at 13:12

answered Sep 3, 2017 at 10:05

Benedikt S. Vogler

5641 gold badge5 silver badges19 bronze badges

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

2 Comments

Subhayan Bhattacharya Over a year ago

when do i encounter a line like : 2 4 R , in which 2 is the parent then how do i search in the btree where this node 2 is located.

Benedikt S. Vogler Over a year ago

Updated my answer. Hope this helps.

Collectives™ on Stack Overflow

How to construct a binary tree from given input

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related