How to implement a binary search tree in Python

Question

This is what I ve got so far but it is not working   class Node      rChild lChild data   None None None      def   init   self key           self rChild   None         self lChild   None         self data   key  class Tree      root size   None 0     def   init   self           self root   None         self size   0      def insert self node someNumber           if node is None              node   Node someNumber          else              if node data  gt  someNumber                  self insert node rchild someNumber              else                  self insert node rchild  someNumber          return  def main        t   Tree       t root   Node 4      t root rchild   Node 5      print t root data  this works     print t root rchild data  this works too     t   Tree       t insert t root 4      t insert t root 5      print t root data  this fails     print t root rchild data  this fails too  if   name         main          main

User · Answer

class Node      rChild lChild parent data   None None None 0      def   init   self key       self rChild   None     self lChild   None     self parent   None     self data   key   class Tree      root size   None 0     def   init   self           self root   None         self size   0     def insert self someNumber           self size   self size 1         if self root is None              self root   Node someNumber          else              self insertWithNode self root  someNumber           def insertWithNode self node someNumber           if node lChild is None and node rChild is None  external node             if someNumber  gt  node data                  newNode   Node someNumber                  node rChild   newNode                 newNode parent   node             else                  newNode   Node someNumber                  node lChild   newNode                 newNode parent   node         else   not external             if someNumber  gt  node data                  if node rChild is not None                      self insertWithNode node rChild  someNumber                  else   if empty node                     newNode   Node someNumber                      node rChild   newNode                     newNode parent   node              else                  if node lChild is not None                      self insertWithNode node lChild  someNumber                  else                      newNode   Node someNumber                      node lChild   newNode                     newNode parent   node                          def printTree self someNode           if someNode is None              pass         else              self printTree someNode lChild              print someNode data             self printTree someNode rChild   def main          t   Tree       t insert 5        t insert 3      t insert 7      t insert 4      t insert 2      t insert 1      t insert 6      t printTree t root   if   name         main         main     My solution

User · Answer

Here is a working solution   class BST      def   init   self data           self root   data         self left   None         self right   None      def insert self data           if self root    None              self root   BST data          elif data  gt  self root              if self right    None                  self right   BST data              else                  self right insert data          elif data  lt  self root              if self left    None                  self left   BST data              else                  self left insert data       def inordertraversal self           if self left    None              self left inordertraversal           print  self root           if self right    None              self right inordertraversal    t   BST 4  t insert 1  t insert 7  t insert 3  t insert 6  t insert 2  t insert 5  t inordertraversal

User · Answer

Here is a quick example of a binary insert   class Node      def   init   self  val           self l child   None         self r child   None         self data   val  def binary insert root  node       if root is None          root   node     else          if root data  gt  node data              if root l child is None                  root l child   node             else                  binary insert root l child  node          else              if root r child is None                  root r child   node             else                  binary insert root r child  node   def in order print root       if not root          return     in order print root l child      print root data     in order print root r child   def pre order print root       if not root          return             print root data     pre order print root l child      pre order print root r child          r   Node 3  binary insert r  Node 7   binary insert r  Node 1   binary insert r  Node 5            3            1   7              5     print  in order   in order print r   print  pre order  pre order print r   in order  1 3 5 7 pre order 3 1 7 5

User · Answer

its easy to implement a BST using two classes  1  Node and 2  Tree Tree class will be just for user interface  and actual methods will be implemented in Node class   class Node         def   init   self val           self value   val         self left   None         self right   None       def  insert self data           if data    self value              return False         elif data  lt  self value              if self left                  return self left  insert data              else                  self left   Node data                  return True         else              if self right                  return self right  insert data              else                  self right   Node data                  return True      def  inorder self           if self              if self left                  self left  inorder               print self value              if self right                  self right  inorder      class Tree         def   init   self           self root   None      def insert self data           if self root              return self root  insert data          else              self root   Node data              return True     def inorder self           if self root is not None              return self root  inorder           else              return False     if   name       main         a   Tree       a insert 16      a insert 8      a insert 24      a insert 6      a insert 12      a insert 19      a insert 29      a inorder     Inorder function for checking whether BST is properly implemented

User · Answer

The problem  or at least one problem with your code is here -  def insert self node someNumber       if node is None          node   Node someNumber      else          if node data  gt  someNumber              self insert node rchild someNumber          else              self insert node rchild  someNumber      return   You see the statement  if node data   someNumber   and the associated  else   statement both have the same code after them  i e you do the same thing whether the if statement is true or false   I d suggest you probably intended to do different things here  perhaps one of these should say self insert node lchild  someNumber

User · Answer

Just something to help you to start on     A  simple idea of  binary tree search would be quite likely be implement in python according the lines   def search node  key       if node is None  return None    key not found     if key lt  node key  return search node left  key      elif key gt  node key  return search node right  key      else  return node value    found key   Now you just need to implement the scaffolding  tree creation and value inserts  and you are done

User · Answer

class TreeNode      def   init   self  value           self value   value         self left   None         self right   None   class BinaryTree      def   init   self  root None           self root   root      def add node self  node  value                       Node points to the left of value if node  gt  value  right otherwise          BST cannot have duplicate values                     if node is not None              if value  lt  node value                  if node left is None                      node left   TreeNode value                  else                      self add node node left  value              else                  if node right is None                      node right   TreeNode value                  else                      self add node node right  value          else              self root   TreeNode value       def search self  value                       Value will be to the left of node if node  gt  value  right otherwise                      node   self root         while node is not None              if node value    value                  return True       node value             if node value  gt  value                  node   node left             else                  node   node right         return False      def traverse inorder self  node                       Traverse the left subtree of a node as much as possible  then traverse         the right subtree  followed by the parent root node                      if node is not None              self traverse inorder node left              print node value              self traverse inorder node right    def main        binary tree   BinaryTree       binary tree add node binary tree root  200      binary tree add node binary tree root  300      binary tree add node binary tree root  100      binary tree add node binary tree root  30      binary tree traverse inorder binary tree root      print binary tree search 200     if   name         main         main

User · Answer

A simple  recursive method with only 1 function and using an array of values   class TreeNode object        def   init   self  value  int  left None  right None           super     init             self value   value         self left   left         self right   right      def   str   self           return str self value    def create node values  lower  upper  - gt  TreeNode      if lower  gt  upper          return None      index    lower   upper     2      value   values index      node   TreeNode value value      node left   create node values  lower  index - 1      node right   create node values  index   1  upper       return node   def print bst node  TreeNode       if node            Simple pre-order traversal when printing the tree         print  node      format node           print bst node left          print bst node right     if   name         main         vals    0  1  2  3  4  5  6      bst   create node vals  lower 0  upper len vals  - 1      print bst bst    As you can see  we really only need 1 method  which is recursive  create node  We pass in the full values array in each create node method call  however  we update the lower and upper index values every time that we make the recursive call     Then  using the lower and upper index values  we calculate the index value of the current node and capture it in value   This value is the value for the current node  which we use to create a node   From there  we set the values of left and right by recursively calling the function  until we reach the end state of the recursion call when lower is greater than upper     Important  we update the value of upper when creating the left side of the tree   Conversely  we update the value of lower when creating the right side of the tree   Hopefully this helps

User · Answer

The Op s Tree insert method qualifies for the  Gross Misnomer of the Week  award -- it doesn t insert anything  It creates a node which is not attached to any other node  not that there are any nodes to attach it to  and then the created node is trashed when the method returns   For the edification of  Hugh Bothwell    gt  gt  gt  class Foo object          bar   None      gt  gt  gt  a   Foo    gt  gt  gt  b   Foo    gt  gt  gt  a bar  gt  gt  gt  a bar   42  gt  gt  gt  b bar  gt  gt  gt  b bar   666  gt  gt  gt  a bar 42  gt  gt  gt  b bar 666  gt  gt  gt

User · Answer

class BST      def   init   self  val None           self left   None         self right   None         self val   val      def   str   self           return    s   s   s      self left  str self val   self right       def isEmpty self           return self left    self right    self val    None      def insert self  val           if self isEmpty                self val   val         elif val  lt  self val              if self left is None                  self left   BST val              else                  self left insert val          else              if self right is None                  self right   BST val              else                  self right insert val   a   BST 1  a insert 2  a insert 3  a insert 0  print a

User · Answer

I find the solutions a bit clumsy on the insert part  You could return the root reference and simplify it a bit   def binary insert root  node       if root is None          return node     if root data  gt  node data          root l child   binary insert root l child  node      else          root r child   binary insert root r child  node      return root

User · Answer

Another Python BST solution  class Node object       def   init   self  value           self left node   None         self right node   None         self value   value      def   str   self           return    s   s   s      self left node  self value  self right node       def insertValue self  new value                       1  if current Node doesnt have value then assign to self         2  new value lower than current Node s value then go left         2  new value greater than current Node s value then go right          return                      if self value              if new value  lt  self value                    add to left                 if self left node is None     reached start add value to start                     self left node   Node new value                  else                      self left node insertValue new value     search             elif new value  gt  self value                    add to right                 if self right node is None     reached end add value to end                     self right node   Node new value                  else                      self right node insertValue new value     search         else              self value   new value      def findValue self  value to find                       1  value to find is equal to current Node s value then found         2  if value to find is lower than Node s value then go to left         3  if value to find is greater than Node s value then go to right                     if value to find    self value              return  Found          elif value to find  lt  self value and self left node              return self left node findValue value to find          elif value to find  gt  self value and self right node              return self right node findValue value to find          return  Not Found       def printTree self                       Nodes will be in sequence         1  Print LHS items         2  Print value of node         3  Print RHS items                     if self left node              self left node printTree           print self value           if self right node              self right node printTree        def isEmpty self           return self left node    self right node    self value    None   def main        root node   Node 12      root node insertValue 6      root node insertValue 3      root node insertValue 7         should return 3 6 7 12     root node printTree          should return found     root node findValue 7        should return found     root node findValue 3        should return Not found     root node findValue 24   if   name         main         main

User · Answer

class Node       rChild lChild data   None None None   This is wrong - it makes your variables class variables - that is  every instance of Node uses the same values  changing rChild of any node changes it for all nodes    This is clearly not what you want  try  class Node       def   init   self  key           self rChild   None         self lChild   None         self data   key   now each node has its own set of variables  The same applies to your definition of Tree   class Tree      root size   None 0       lt - lose this line      def   init   self           self root   None         self size   0   Further  each class should be a  new-style  class derived from the  object  class and should chain back to object   init       class Node object        def   init   self  data  rChild None  lChild None           super Node self    init             self data     data         self rChild   rChild         self lChild   lChild  class Tree object       def   init   self           super Tree self    init             self root   None         self size   0   Also  main   is indented too far - as shown  it is a method of Tree which is uncallable because it does not accept a self argument   Also  you are modifying the object s data directly  t root   Node 4   which kind of destroys encapsulation  the whole point of having classes in the first place   you should be doing something more like  def main        t   Tree       t add 4        lt - let the tree create a data Node and insert it     t add 5

User · Answer

Another Python BST with sort key  defaulting to value   LEFT   0 RIGHT   1 VALUE   2 SORT KEY   -1  class BinarySearchTree object        def   init   self  sort key None           self  root                self  sort key   sort key         self  len   0    def insert self  val       if self  sort key is None          sort key   val    if no sort key  sort key is value     else          sort key   self  sort key val       node   self  root     while node          if sort key  lt  node  SORT KEY               node   node LEFT          else              node   node RIGHT       if sort key is val          node               val      else          node               val  sort key      self  len    1  def minimum self       return self  extreme node LEFT  VALUE   def maximum self       return self  extreme node RIGHT  VALUE   def find self  sort key       return self  find sort key  VALUE   def  extreme node self  side       if not self  root          raise IndexError  Empty       node   self  root     while node side           node   node side      return node  def  find self  sort key       node   self  root     while node          node key   node SORT KEY          if sort key  lt  node key              node   node LEFT          elif sort key  gt  node key              node   node RIGHT          else              return node     raise KeyError   r not found    sort key

User · Answer

Here is a compact  object oriented  recursive implementation       class BTreeNode object           def   init   self  data               self data   data             self rChild   None             self lChild   None      def   str   self           return  self lChild   str         lt -  if self lChild    None else       self data   str         - gt     self rChild   str     if self rChild    None else          def insert self  btreeNode           if self data  gt  btreeNode data   insert left             if self lChild    None                  self lChild   btreeNode             else                  self lChild insert btreeNode          else   insert right             if self rChild    None                  self rChild   btreeNode             else                  self rChild insert btreeNode    def main        btreeRoot   BTreeNode 5      print  inserted  s    5  btreeRoot      btreeRoot insert BTreeNode 7       print  inserted  s    7  btreeRoot      btreeRoot insert BTreeNode 3       print  inserted  s    3  btreeRoot      btreeRoot insert BTreeNode 1       print  inserted  s    1  btreeRoot      btreeRoot insert BTreeNode 2       print  inserted  s    2  btreeRoot      btreeRoot insert BTreeNode 4       print  inserted  s    4  btreeRoot      btreeRoot insert BTreeNode 6       print  inserted  s    6  btreeRoot   The output of the above main   is   inserted 5  5 inserted 7  5- gt 7 inserted 3  3 lt -5- gt 7 inserted 1  1 lt -3 lt -5- gt 7 inserted 2  1- gt 2 lt -3 lt -5- gt 7 inserted 4  1- gt 2 lt -3- gt 4 lt -5- gt 7 inserted 6  1- gt 2 lt -3- gt 4 lt -5- gt 6 lt -7

User · Answer

def BinaryST list1 key       start   0     end   len list1      print  Length of List    end       for i in range end           for j in range 0  end-i-1               if list1 j   gt  list1 j 1                    temp   list1 j                  list1 j    list1 j 1                  list1 j 1    temp      print  Order List    list1       mid   int  start end  2      print  Mid Index    mid       if key    list1 mid            print key   is on   mid   Index        elif key  gt  list1 mid            for rindex in range mid 1 end               if key    list1 rindex                    print key   is on   rindex   Index                   break             elif rindex    end-1                   print  Given key    key   is not in List                   break             else                  continue      elif key  lt  list1 mid            for lindex in range 0 mid               if key    list1 lindex                    print key   is on   lindex   Index                   break             elif lindex    mid-1                   print  Given key    key   is not in List                   break             else                  continue   size   int input  Enter Size of List      list1      for e in range size       ele   int input  Enter Element in List          list1 append ele   key   int input   nEnter Key for Search       print   nUnorder List    list1  BinaryST list1 key

User · Answer

The accepted answer neglects to set a parent attribute for each node inserted  without which one cannot implement a successor method which finds the successor in an in-order tree walk in O h  time  where h is the height of the tree  as opposed to the O n  time needed for the walk    Here is an implementation based on the pseudocode given in Cormen et al   Introduction to Algorithms  including assignment of a parent attribute and a successor method   class Node object       def   init   self  key           self key   key         self left   None         self right   None         self parent   None   class Tree object       def   init   self  root None           self root   root      def insert self  z           y   None         x   self root         while x is not None              y   x             if z key  lt  x key                  x   x left             else                  x   x right         z parent   y         if y is None              self root   z         Tree was empty         elif z key  lt  y key              y left   z         else              y right   z       staticmethod     def minimum x           while x left is not None              x   x left         return x       staticmethod     def successor x           if x right is not None              return Tree minimum x right          y   x parent         while y is not None and x    y right              x   y             y   y parent         return y   Here are some tests to show that the tree behaves as expected for the example given by DTing   import pytest   pytest fixture def tree        t   Tree       t insert Node 3       t insert Node 1       t insert Node 7       t insert Node 5       return t  def test tree insert tree       assert tree root key    3     assert tree root left key    1     assert tree root right key    7     assert tree root right left key    5  def test tree successor tree       assert Tree successor tree root left  key    3     assert Tree successor tree root right left  key    7  if   name         main         pytest main    file

User · Answer

The following code is basic on  DTing   s answer and what I learn from class  which uses a while loop to insert  indicated in the code     class Node      def   init   self  val           self l child   None         self r child   None         self data   val   def binary insert root  node       y   None     x   root     z   node      while loop here     while x is not None          y   x         if z data  lt  x data              x   x l child         else              x   x r child     z parent   y     if y    None          root   z     elif z data  lt  y data          y l child   z     else          y r child   z   def in order print root       if not root          return     in order print root l child      print root data      in order print root r child    r   Node 3  binary insert r  Node 7   binary insert r  Node 1   binary insert r  Node 5    in order print r

[python] How to implement a binary search tree in Python?

Examples related to python

Examples related to oop

Examples related to class

Examples related to data-structures

Examples related to binary-search-tree