CODEWITHSUNDEEP
pythonalgorithmbinary-tree
aol
aol

Reputation: 55

How to find position of nodes in binary tree?

4 0 2
0 1
0 3
2 3
0
3

I'm trying to find effective solution to the above problem.

Given input first line is: number of nodes in binary tree=4, root=0, depths=2

Edges or nodes on the edge are not given in any specific order, but edge that connects node to left child appears in input.

and the last two lines to find the position of 0 and 3 ,its output is

 1 2
 3 1

Tree can have more than million nodes and build tree using

I couldn't find how to represent tree in such way that it would be possible to find coordinates of nodes

updated code

class node:
    def __init__(self, x):
        self.x=4
        self.l=2
        self.r=0
        self.id=id


    def recurse(node,id, depth = -1, position=-1, max_depth=-1):
        depth=depth+1
        current_depth=depth
        max_depth=max(max_depth,current_depth)

        matchl=False
        matchr=False

        if node.l :
            (depthl,position,max_depth,matchl)=node.recurse(node.l,id,current_depth,position,max_depth)

        positionl = position
        position = position + 1
        current_position=position


        if node.r:
            (depth,position,max_depth,matchr)=node.recurse(node.r,id,current_depth,position,max_depth)

        if matchl:
            return (depthl,positionl,max_depth,True)

        if node.x==id:
            return (current_depth,current_position,max_depth,True)
        return (depth,position,max_depth,matchr)


n2=node(2)
n3=node(3)
n1=node(1)
n0=node(0)

n0.l=n1
n0.r=n3
n3.l=n2

(depth,position,max_depth,match)=node.recurse(n0,3)
if match:
   answer = (position, max_depth - depth )

Upvotes: 3

Views: 2092

Answers (2)

xvan
xvan

Reputation: 4855

The way your problem is given assumes no two nodes can share a column, and that the left node is filled first, given that condition is easy to recruse a node position if you traverse the tree in the correct order (left leaf, node, right leaf):

The following code is untested, but should give you an idea of the algorithm:

def recurse( node,  id, depth = -1, position=-1, max_depth=-1):
   depth=depth+1
   current_depth=depth

   max_depth=max(max_depth,current_depth)

   matchl=False
   matchr=False

   if node.l :
       (depthl,position,max_depth,matchl)=recurse(node.l,id,current_depth,position,max_depth)

   positionl = position
   position = position + 1
   current_position=position


   if node.r:
      (depth,position,max_depth,matchr)=recurse(node.r,id,current_depth,position,max_depth)

   if matchl:
      return (depthl,positionl,max_depth,True)

   if node.x==id:
      return (current_depth,current_position,max_depth,True)

   return (depth,position,max_depth,matchr)

Usage

(depth,position,match, max_depth) = recurse(root_node,target_id)

Example:

n2=node(2)
n3=node(3)
n1=node(1)
n0=node(0)

n0.l=n1
n0.r=n3
n3.l=n2

(depth,position,max_depth,match)=recurse(n0,3)
if match:
   answer = (position, max_depth - depth )

Upvotes: 1

Sci Prog
Sci Prog

Reputation: 2691

Your questions seems to imply that the graphical representation of a tree is unique, and it is not the case. You should search for "Tree Drawing Algorithms".

For example, a quick search yielded http://cs.brown.edu/~rt/gdhandbook/chapters/trees.pdf and http://www.cs.unc.edu/techreports/89-034.pdf

Upvotes: 0

Related Questions