title: binary tree add left and add right nodes not adding
body: <p>I'm reading the following data as part of an assignment into a <strong>binary tree</strong> (not a <strong>strict binary search tree</strong>):</p>
  
  <pre><code>5
  4 1 2
  2 3 4
  5 -1 -1
  1 -1 -1
  3 -1 -1
  </code></pre>
  
  <p>They're being read into three lists in python <code>self.key</code>, <code>self.left</code> and <code>self.right</code> where the first line has the integer <code>n</code> is the number of nodes. The next n lines are key, left, right. Where left is the key of the left child of the parent is <code>key[left]</code> and likewise the key of the right child is <code>key[right]</code>, so for example the first line is the key of 4 is the root and <code>key[1]</code> meaning 2 is the left child of 4 and <code>key[2]</code> meaning 5 is the right child of 4 and so on and -1 for left and right means this key is a leaf:</p>
  
  <p><a href="http://i.stack.imgur.com/5nTYl.jpg" rel="nofollow">Tree structure for this example</a></p>
  
  <p>The problem is the left and right children of the root are being added but none of the children of these are being added. Am I correctly adding nodes to the tree? I cannot just add them based on value of the key because it's not a <strong>strict binary search tree</strong> as some other examples make clear, such as <em>root = 0</em> and <em>left child = 70</em> and <em>right child = 20</em>. The output of inOrder traversal is <code>2 4 5</code> (should be <code>1 2 3 4 5</code>) which leads me to believe I'm not adding the further nodes. Any help on the adding methods would be appreciated...</p>
  
  <pre><code>import sys, threading
  sys.setrecursionlimit(10**6) # max depth of recursion
  threading.stack_size(2**27)  # new thread will get stack of such size
  
  
  class Node:
      def __init__(self, val):
          self.l = None
          self.r = None
          self.v = val
  
  class Tree:
      def __init__(self):
          self.root = None
  
      def getRoot(self):
          return self.root
  
      def add_root(self, val):
          if(self.root is None):
              self.root = Node(val)
  
      def add_left(self, val, node):
          if(node.l is None):
              node.l = Node(val)
  
      def add_right(self, val, node):
          if(node.r is None):
              node.r = Node(val)
  
      def deleteTree(self):
          # garbage collector will do this for us. 
          self.root = None
  
  
      def inOrder(self):
          self.result = []
          if(self.root is not None):
              self._inOrder(self.root, self.result)
              return self.result
          else:
              print('root is None')
  
      def _inOrder(self, node, result):
          if(node != None):
              self._inOrder(node.l, self.result)
              self.result.append(node.v)
              self._inOrder(node.r, self.result)
  
      def read(self):
          self.n = int(sys.stdin.readline())
          self.key = [0 for i in range(self.n)]
          self.left = [0 for i in range(self.n)]
          self.right = [0 for i in range(self.n)]
          for i in range(self.n):
              [a, b, c] = map(int, sys.stdin.readline().split())
              self.key[i] = a
              self.left[i] = b
              self.right[i] = c
  
          #adding root
          self.add_root(self.key[0])
          if self.left[0] != -1: 
              #add left of root
              self.add_left(self.key[self.left[0]], self.root)
          if self.right[0] != -1:
              #add right of root
              self.add_right(self.key[self.right[0]], self.root)
  
          #where it is not adding left and right nodes
          for i in range(1, self.n):
              if self.left[i] != -1:
                  # adding the other left nodes
                  self.add_left(self.key[self.left[i]], Node(self.key[i]))
              if self.right[i] != -1:
                  # adding the other right nodes
                  self.add_right(self.key[self.right[i]], Node(self.key[i]))
  
  def main():
      tree = Tree()
      tree.read()
      print(" ".join(str(x) for x in tree.inOrder()))
      #print(" ".join(str(x) for x in tree.preOrder()))
      #print(" ".join(str(x) for x in tree.postOrder()))
  
  threading.Thread(target=main).start()
  </code></pre>