How to implement a binary tree

Question

Which is the best data structure that can be used to implement a binary tree in Python

User · Answer

class Node       quot  quot  quot      single Node for tree      quot  quot  quot       def   init   self  data           self data   data         self right   None         self left   None   class binaryTree       quot  quot  quot      binary tree implementation      quot  quot  quot       def   init   self           self root   None      def push self  element  node None           if node is None              node   self root          if self root is None              self root   Node element           else              if element  lt  node data                  if node left is not None                      self push element  node left                  else                      node left   Node element              else                  if node right is not None                      self push element  node right                  else                      node right   Node element       def   str   self           self printInorder self root          return  quot  n quot       def printInorder self  node            quot  quot  quot          print tree in inorder          quot  quot  quot          if node is not None              self printInorder node left              print node data              self printInorder node right    def main         quot  quot  quot      Main code and logic comes here      quot  quot  quot      tree   binaryTree       tree push 5      tree push 3      tree push 1      tree push 3      tree push 0      tree push 2      tree push 9      tree push 10      print tree    if   name       quot   main   quot       main

User · Answer

You can make your own BinaryTree data structure in Python the OOP way  or building a class   You can separate two class in here  Node and BinaryTree  The  quot Node quot  class will be responsible for creating individual node objects for the BinaryTree while the  quot BinaryTree quot  class is what you ll need to implement the binary tree on top of the  quot Node quot  class  Here s what I coded when I m studying it back then  class TreeNode       def   init   self  data None           self data   data         self left   None         self right   None      def   str   self           return f Node Data  self data   Left  self left   Right  self right         def   repr   self           return self   str          def get data self           return self data      def set data self  data           self data   data      def get left self           return self left      def set left self  left           self left   left      def get right self           return self right      def set right self  right           self right   right  class BinaryTree       def   init   self  root None           self root   TreeNode root       def   str   self           return f BinaryTree  self root         def   repr   self           return f BinaryTree  self root         def insert self  data             if empty tree         if self root get data   is None              return self root set data data          new node   TreeNode data          current   self root         while True              if data  lt  current get data                    if current get left   is None                      return current set left new node                  current   current get left                   continue             elif data  gt  current get data                    if current get right   is None                      return current set right new node                  current   current get right                   continue             return        still needs other methods like the delete method  but you can       try it out yourself     def delete self  node           pass  def main        myTree   BinaryTree       myTree insert 5      myTree insert 3      myTree insert 4      myTree insert 2      myTree insert 8      myTree insert 9      myTree insert 6      print myTree   if   name         main         main

User · Answer

Binary Tree in Python   class Tree object       def   init   self           self data None         self left None         self right None     def insert self  x  root           if root  None              t node x              t data x             t right None             t left None             root t             return root         elif x lt root data              root left self insert x  root left          else              root right self insert x  root right          return root      def printTree self  t           if t  None              return          self printTree t left          print t data         self printTree t right   class node object       def   init   self  x           self x x  bt Tree   root None n int raw input    a    for i in range n       a append int raw input     for i in range n       root bt insert a i   root  bt printTree root

User · Answer

A Node-based class of connected nodes is a standard approach   These can be hard to visualize   Motivated from an essay on Python Patterns - Implementing Graphs  consider a simple dictionary   Given  A binary tree                 a                                b   c                                d   e   f   Code  Make a dictionary of unique nodes   tree         a     b    c        b     d    e        c    None   f        d    None  None       e    None  None       f    None  None         Details   Each key-value pair is a unique node pointing to its children  A list  or tuple  holds an ordered pair of left right children  With a dict having ordered insertion  assume the first entry is the root  Common methods can be functions that mutate or traverse the dict  see find all paths        Tree-based functions often include the following common operations    traverse  yield each node in a given order  usually left-to-right    breadth-first search  BFS   traverse levels  depth-first search  DFS   traverse branches first  pre- in- post-order   insert  add a node to the tree depending on the number of children remove  remove a node depending on the number of children update  merge missing nodes from one tree to the other visit  yield the value of a traversed node   Try implementing all of these operations  Here we demonstrate one of these functions - a BFS traversal   Example  import collections as ct   def traverse tree          Yield nodes from a tree via BFS         q   ct deque                                             1     root   next iter tree                                    2     q append root       while q          node   q popleft           children   filter None  tree get node           for n in children                                    3              q append n          yield node     list traverse tree       a    b    c    d    e    f     This is a breadth-first search  level-order  algorithm applied to a dict of nodes and children      Initialize a FIFO queue   We use a deque  but a queue or a list works  the latter is inefficient   Get and enqueue the root node  assumes the root is the first entry in the dict  Python 3 6    Iteratively dequeue a node  enqueue its children and yield the node value    See also this in-depth tutorial on trees     Insight  Something great about traversals in general  we can easily alter the latter iterative approach to depth-first search  DFS  by simply replacing the queue with a stack  a k a LIFO Queue    This simply means we dequeue from the same side that we enqueue   DFS allows us to search each branch   How   Since we are using a deque  we can emulate a stack by changing node   q popleft   to node   q pop    right    The result is a right-favored  pre-ordered DFS    a    c    f    b    e    d

User · Answer

What you need for interviews  A Node class is the sufficient data structure to represent a binary tree     While other answers are mostly correct  they are not required for a binary tree  no need to extend object class  no need to be a BST  no need to import deque     class Node       def   init   self  value   None           self left    None         self right   None         self value   value   Here is an example of a tree    n1   Node 1  n2   Node 2  n3   Node 3  n1 left    n2 n1 right   n3   In this example n1 is the root of the tree having n2  n3 as its children

User · Answer

A good implementation of binary search tree  taken from here       A binary search Tree     from   future   import print function class Node       def   init   self  label  parent           self label   label         self left   None         self right   None          Added in order to delete a node easier         self parent   parent      def getLabel self           return self label      def setLabel self  label           self label   label      def getLeft self           return self left      def setLeft self  left           self left   left      def getRight self           return self right      def setRight self  right           self right   right      def getParent self           return self parent      def setParent self  parent           self parent   parent  class BinarySearchTree       def   init   self           self root   None      def insert self  label             Create a new Node         new node   Node label  None            If Tree is empty         if self empty                self root   new node         else               If Tree is not empty             curr node   self root              While we don t get to a leaf             while curr node is not None                   We keep reference of the parent node                 parent node   curr node                  If node label is less than current node                 if new node getLabel    lt  curr node getLabel                     We go left                     curr node   curr node getLeft                   else                       Else we go right                     curr node   curr node getRight                We insert the new node in a leaf             if new node getLabel    lt  parent node getLabel                    parent node setLeft new node              else                  parent node setRight new node               Set parent to the new node             new node setParent parent node             def delete self  label           if  not self empty                  Look for the node with that label             node   self getNode label               If the node exists             if node is not None                    If it has no children                 if node getLeft   is None and node getRight   is None                       self   reassignNodes node  None                      node   None                  Has only right children                 elif node getLeft   is None and node getRight   is not None                       self   reassignNodes node  node getRight                     Has only left children                 elif node getLeft   is not None and node getRight   is None                       self   reassignNodes node  node getLeft                     Has two children                 else                       Gets the max value of the left branch                     tmpNode   self getMax node getLeft                         Deletes the tmpNode                     self delete tmpNode getLabel                         Assigns the value to the node to delete and keesp tree structure                     node setLabel tmpNode getLabel         def getNode self  label           curr node   None          If the tree is not empty         if not self empty                  Get tree root             curr node   self getRoot                While we don t find the node we look for              I am using lazy evaluation here to avoid NoneType Attribute error             while curr node is not None and curr node getLabel   is not label                   If node label is less than current node                 if label  lt  curr node getLabel                         We go left                     curr node   curr node getLeft                   else                       Else we go right                     curr node   curr node getRight           return curr node      def getMax self  root   None           if root is not None               curr node   root         else               We go deep on the right branch             curr node   self getRoot           if not self empty                 while curr node getRight   is not None                   curr node   curr node getRight           return curr node      def getMin self  root   None           if root is not None               curr node   root         else               We go deep on the left branch             curr node   self getRoot           if not self empty                 curr node   self getRoot               while curr node getLeft   is not None                   curr node   curr node getLeft           return curr node      def empty self           if self root is None              return True         return False      def   InOrderTraversal self  curr node           nodeList              if curr node is not None              nodeList insert 0  curr node              nodeList   nodeList   self   InOrderTraversal curr node getLeft                nodeList   nodeList   self   InOrderTraversal curr node getRight            return nodeList      def getRoot self           return self root      def   isRightChildren self  node           if node    node getParent   getRight                 return True         return False      def   reassignNodes self  node  newChildren           if newChildren is not None               newChildren setParent node getParent            if node getParent   is not None                If it is the Right Children             if self   isRightChildren node                    node getParent   setRight newChildren              else                   Else it is the left children                 node getParent   setLeft newChildren        This function traversal the tree  By default it returns an      In order traversal list  You can pass a function to traversal      The tree as needed by client code     def traversalTree self  traversalFunction   None  root   None           if traversalFunction is None                Returns a list of nodes in preOrder by default             return self   InOrderTraversal self root          else               Returns a list of nodes in the order that the users wants to             return traversalFunction self root        Returns an string of all the nodes labels in the list       In Order Traversal     def   str   self           list   self   InOrderTraversal self root          str              for x in list              str   str         x getLabel     str             return str  def InPreOrder curr node       nodeList          if curr node is not None          nodeList   nodeList   InPreOrder curr node getLeft            nodeList insert 0  curr node getLabel            nodeList   nodeList   InPreOrder curr node getRight        return nodeList  def testBinarySearchTree        r        Example                   8                                      3   10                                       1   6    14                                          4   7 13               r        Example After Deletion                   7                                      1   4              t   BinarySearchTree       t insert 8      t insert 3      t insert 6      t insert 1      t insert 10      t insert 14      t insert 13      t insert 4      t insert 7        Prints all the elements of the list in order traversal     print t   str           if t getNode 6  is not None           print  The label 6 exists       else          print  The label 6 doesn t exist        if t getNode -1  is not None           print  The label -1 exists       else          print  The label -1 doesn t exist        if not t empty             print   Max Value     t getMax   getLabel             print   Min Value     t getMin   getLabel          t delete 13      t delete 10      t delete 8      t delete 3      t delete 6      t delete 14        Gets all the elements of the tree In pre order      And it prints them     list   t traversalTree InPreOrder  t root      for x in list          print x   if   name         main         testBinarySearchTree

User · Answer

This implementation supports insert  find and delete operations without destroy the structure of the tree  This is not a banlanced tree     Class for construct the nodes of the tree   Subtrees  class Node  def   init   self  key  parent node   None       self left   None     self right   None     self key   key     if parent node    None          self parent   self     else          self parent   parent node    Class with the  structure of the tree     This Tree is not balanced  class Tree  def   init   self       self root   None    Insert a single element def insert self  x       if self root    None           self root   Node x      else          self  insert x  self root   def  insert self  x  node       if x  lt  node key           if node left    None               node left   Node x  node          else              self  insert x  node left      else          if node right    None               node right   Node x  node          else              self  insert x  node right     Given a element  return a node in the tree with key x   def find self  x       if self root    None           return None     else          return self  find x  self root  def  find self  x  node       if x    node key           return node     elif x  lt  node key           if node left    None               return None         else              return self  find x  node left      elif x  gt  node key           if node right    None               return None         else              return self  find x  node right     Given a node  return the node in the tree with the next largest element  def next self  node       if node right    None          return self  left descendant node right      else          return self  right ancestor node   def  left descendant self  node       if node left    None          return node     else          return self  left descendant node left   def  right ancestor self  node       if node key  lt   node parent key          return node parent     else          return self  right ancestor node parent     Delete an element of the tree def delete self  x       node   self find x      if node    None          print x   isn t in the tree       else          if node right    None              if node left    None                  if node key  lt  node parent key                      node parent left   None                     del node   Clean garbage                 else                      node parent right   None                     del Node   Clean garbage             else                  node key   node left key                 node left   None         else              x   self next node              node key   x key             x   None     tests t   Tree   t insert 5  t insert 8  t insert 3  t insert 4  t insert 6  t insert 2   t delete 8  t delete 5   t insert 9  t insert 1   t delete 2  t delete 100     Remember  Find method return the node object     To return a number use t find n    key   But it will cause an error if the number is not in the tree  print t find 5    print t find 8   print t find 4   print t find 6   print t find 9

User · Answer

I know many good solutions have already been posted but I usually have a different approach for binary trees  going with some Node class and implementing it directly is more readable but when you have a lot of nodes it can become very greedy regarding memory  so I suggest adding one layer of complexity and storing the nodes in a python list  and then simulating a tree behavior using only the list   You can still define a Node class to finally represent the nodes in the tree when needed  but keeping them in a simple form  value  left  right  in a list will use half the memory or less   Here is a quick example of a Binary Search Tree class storing the nodes in an array  It provides basic fonctions such as add  remove  find         Basic Binary Search Tree class without recursion           author       fbparis   class Node object         slots      value    parent    left    right      def   init   self  value  parent None  left None  right None           self value   value         self parent   parent         self left   left         self right   right      def   repr   self           return   lt  s object at  s  parent  s  left  s  right  s  value  s gt      self   class     name    hex id self    self parent  self left  self right  self value   class BinarySearchTree object         slots       tree      def   init   self   args           self  tree              if args              for x in args 0                   self add x       def   len   self           return len self  tree       def   repr   self           return   lt  s object at  s with  d nodes gt      self   class     name    hex id self    len self        def   str   self  nodes None  level 0           ret              if nodes is None              if len self                   nodes    0              else                  nodes              for node in nodes              if node is None                  continue             ret     -    level      s n    self  tree node  0              ret    self   str   self  tree node  2 4   level   1          if level    0              ret   ret strip           return ret      def   contains   self  value           if len self               node index   0             while self  tree node index  0     value                  if value  lt  self  tree node index  0                       node index   self  tree node index  2                  else                      node index   self  tree node index  3                  if node index is None                      return False             return True         return False      def   eq   self  other           return self  tree    other  tree      def add self  value           if len self               node index   0             while self  tree node index  0     value                  if value  lt  self  tree node index  0                       b   self  tree node index  2                      k   2                 else                      b   self  tree node index  3                      k   3                 if b is None                      self  tree node index  k    len self                      self  tree append  value  node index  None  None                       break                 node index   b         else              self  tree append  value  None  None  None        def remove self  value           if len self               node index   0             while self  tree node index  0     value                  if value  lt  self  tree node index  0                       node index   self  tree node index  2                  else                      node index   self  tree node index  3                  if node index is None                      raise KeyError             if self  tree node index  2  is not None                  b  d   2  3             elif self  tree node index  3  is not None                  b  d   3  2             else                  i   node index                 b   None             if b is not None                  i   self  tree node index  b                  while self  tree i  d  is not None                      i   self  tree i  d                  p   self  tree i  1                  b   self  tree i  b                  if p    node index                      self  tree p  5-d    b                 else                      self  tree p  d    b                 if b is not None                      self  tree b  1    p                 self  tree node index  0    self  tree i  0              else                  p   self  tree i  1                  if p is not None                      if self  tree p  2     i                          self  tree p  2    None                     else                          self  tree p  3    None             last   self  tree pop               n   len self              if i  lt  n                  self  tree i    last                    if last 2  is not None                      self  tree last 2   1    i                 if last 3  is not None                      self  tree last 3   1    i                 if self  tree last 1   2     n                      self  tree last 1   2    i                 else                      self  tree last 1   3    i         else              raise KeyError      def find self  value           if len self               node index   0             while self  tree node index  0     value                  if value  lt  self  tree node index  0                       node index   self  tree node index  2                  else                      node index   self  tree node index  3                  if node index is None                      return None             return Node  self  tree node index           return None   I ve added a parent attribute so that you can remove any node and maintain the BST structure   Sorry for the readability  especially for the  remove  function  Basically  when a node is removed  we pop the tree array and replace it with the last element  except if we wanted to remove the last node   To maintain the BST structure  the removed node is replaced with the max of its left children or the min of its right children and some operations have to be done in order to keep the indexes valid but it s fast enough   I used this technique for more advanced stuff to build some big words dictionaries with an internal radix trie and I was able to divide memory consumption by 7-8  you can see an example here  https   gist github com fbparis b3ddd5673b603b42c880974b23db7cda

User · Answer

I can t help but notice that most answers here are implementing a Binary Search Tree  Binary Search Tree    Binary Tree    A Binary Search Tree has a very specific property  for any node X  X s key is larger than the key of any descendent of its left child  and smaller than the key of any descendant of its right child  A Binary Tree imposes no such restriction  A Binary Tree is simply a data structure with a  key  element  and two children  say  left  and  right   A Tree is an even more general case of a Binary Tree where each node can have an arbitrary number of children  Typically  each node has a  children  element which is of type list array    Now  to answer the OP s question  I am including a full implementation of a Binary Tree in Python  The underlying data structure storing each BinaryTreeNode is a dictionary  given it offers optimal O 1  lookups  I ve also implemented depth-first and breadth-first traversals  These are very common operations performed on trees   from collections import deque  class BinaryTreeNode      def   init   self  key  left None  right None           self key   key         self left   left         self right   right      def   repr   self           return   s l    s  r    s      self key  self left  self right       def   eq   self  other           if self key    other key and               self right    other right and                   self left    other left              return True         else              return False  class BinaryTree      def   init   self  root key None             maps from BinaryTreeNode key to BinaryTreeNode instance            Thus  BinaryTreeNode keys must be unique          self nodes              if root key is not None                create a root BinaryTreeNode             self root   BinaryTreeNode root key              self nodes root key    self root      def add self  key  left key None  right key None           if key not in self nodes                BinaryTreeNode with given key does not exist  create it             self nodes key    BinaryTreeNode key            invariant  self nodes key  exists            handle left child         if left key is None              self nodes key  left   None         else              if left key not in self nodes                  self nodes left key    BinaryTreeNode left key                invariant  self nodes left key  exists             self nodes key  left   self nodes left key             handle right child         if right key    None              self nodes key  right   None         else              if right key not in self nodes                  self nodes right key    BinaryTreeNode right key                invariant  self nodes right key  exists             self nodes key  right   self nodes right key       def remove self  key           if key not in self nodes              raise ValueError   s not in tree    key            remove key from the list of nodes         del self nodes key            if node removed is left right child  update parent node         for k in self nodes              if self nodes k  left and self nodes k  left key    key                  self nodes k  left   None             if self nodes k  right and self nodes k  right key    key                  self nodes k  right   None         return True      def  height self  node           if node is None              return 0         else              return 1   max self  height node left   self  height node right        def height self           return self  height self root       def size self           return len self nodes       def   repr   self           return str self traverse inorder self root        def bfs self  node           if not node or node not in self nodes              return         reachable                  q   deque             add starting node to queue         q append node          while len q               visit   q popleft                 add currently visited BinaryTreeNode to list             reachable append visit                add left right children as needed             if visit left                  q append visit left              if visit right                  q append visit right          return reachable        visit left child  root  then right child     def traverse inorder self  node  reachable None           if not node or node key not in self nodes              return         if reachable is None              reachable              self traverse inorder node left  reachable          reachable append node key          self traverse inorder node right  reachable          return reachable        visit left and right children  then root       root of tree is always last to be visited     def traverse postorder self  node  reachable None           if not node or node key not in self nodes              return         if reachable is None              reachable              self traverse postorder node left  reachable          self traverse postorder node right  reachable          reachable append node key          return reachable        visit root  left  then right children       root is always visited first     def traverse preorder self  node  reachable None           if not node or node key not in self nodes              return         if reachable is None              reachable              reachable append node key          self traverse preorder node left  reachable          self traverse preorder node right  reachable          return reachable

User · Answer

import random  class TreeNode      def   init   self  key           self key   key         self left   None         self right   None         self p   None  class BinaryTree      def   init   self           self root   None      def length self           return self size      def inorder self  node           if node    None              return None         else              self inorder node left              print node key              self inorder node right       def search self  k           node   self root         while node    None              if node key    k                  return node             if node key  gt  k                  node   node left             else                  node   node right         return None      def minimum self  node           x   None         while node left    None              x   node left             node   node left         return x      def maximum self  node           x   None         while node right    None              x   node right             node   node right         return x      def successor self  node           parent   None         if node right    None              return self minimum node right          parent   node p         while parent    None and node    parent right              node   parent             parent   parent p         return parent      def predecessor self  node           parent   None         if node left    None              return self maximum node left          parent   node p         while parent    None and node    parent left              node   parent             parent   parent p         return parent      def insert self  k           t   TreeNode k          parent   None         node   self root         while node    None              parent   node             if node key  gt  t key                  node   node left             else                  node   node right         t p   parent         if parent    None              self root   t         elif t key  lt  parent key              parent left   t         else              parent right   t         return t       def delete self  node           if node left    None              self transplant node  node right          elif node right    None              self transplant node  node left          else              succ   self minimum node right              if succ p    node                  self transplant succ  succ right                  succ right   node right                 succ right p   succ             self transplant node  succ              succ left   node left             succ left p   succ      def transplant self  node  newnode           if node p    None              self root   newnode         elif node    node p left              node p left   newnode         else              node p right   newnode         if newnode    None              newnode p   node p

User · Answer

A little more  Pythonic     class Node      def   init   self  value           self value   value         self left   None         self right   None      def   repr   self           return str self value     class BST      def   init   self           self root   None      def   repr   self           self sorted              self get inorder self root          return str self sorted       def get inorder self  node           if node              self get inorder node left              self sorted append str node value               self get inorder node right       def add self  value           if not self root              self root   Node value          else              self  add self root  value       def  add self  node  value           if value  lt   node value              if node left                  self  add node left  value              else                  node left   Node value          else              if node right                  self  add node right  value              else                  node right   Node value     from random import randint  bst   BST    for i in range 100       bst add randint 1  1000   print  bst

User · Answer

Simple implementation of BST in Python   class TreeNode      def   init   self  value           self left   None         self right   None         self data   value  class Tree      def   init   self           self root   None      def addNode self  node  value           if node  None               self root   TreeNode value          else              if value lt node data                   if node left  None                       node left   TreeNode value                  else                      self addNode node left  value              else                  if node right  None                       node right   TreeNode value                  else                      self addNode node right  value       def printInorder self  node           if node  None               self printInorder node left              print node data              self printInorder node right   def main        testTree   Tree       testTree addNode testTree root  200      testTree addNode testTree root  300      testTree addNode testTree root  100      testTree addNode testTree root  30      testTree printInorder testTree root

User · Answer

I want to show a variation of  apadana s method  which is more useful when there is a considerable number of nodes       Suppose we have the following tree       10              11      9               7   12  15   8       Step 1 - Create nodes - Use a list instead of defining each node separately nlist    10 11 7 9 15 8 12   n      for i in range len nlist    n append Node nlist i       Step 2 - Set each node position n 0  left    n 1  n 1  left   n 2  n 0  right   n 3  n 3  left   n 4  n 3  right   n 5  n 1  right   n 6

User · Answer

A very quick  n dirty way of implementing a binary tree using lists  Not the most efficient  nor does it handle nil values all too well  But it s very transparent  at least to me    def  add node  v       new    v              if node          left  right   node 1           if not left              left extend new          elif not right              right extend new          else               add left  v      else          node extend new   def binary tree s       root          for e in s           add root  e      return root  def traverse n  order       if n          v   n 0          if order     pre               yield v         for left in traverse n 1   order               yield left         if order     in               yield v         for right in traverse n 2   order               yield right         if order     post               yield v   Constructing a tree from an iterable     gt  gt  gt  tree   binary tree  A B C D E  split      gt  gt  gt  print tree    A     B     D              E               C              Traversing a tree     gt  gt  gt  list traverse tree   pre     list traverse tree   in     list traverse tree   post        A    B    D    E    C        D    B    E    A    C        D    E    B    C    A

User · Answer

simple binary tree   in this implementation  a node is inserted between an existing node and the root   class BinaryTree         def   init   self rootid         self left   None       self right   None       self rootid   rootid      def getLeftChild self           return self left     def getRightChild self           return self right     def setNodeValue self value           self rootid   value     def getNodeValue self           return self rootid      def insertRight self newNode           if self right    None              self right   BinaryTree newNode          else              tree   BinaryTree newNode              tree right   self right             self right   tree      def insertLeft self newNode           if self left    None              self left   BinaryTree newNode          else              tree   BinaryTree newNode              tree left   self left             self left   tree   def printTree tree           if tree    None              printTree tree getLeftChild                print tree getNodeValue                printTree tree getRightChild         test tree  def testTree        myTree   BinaryTree  Maud       myTree insertLeft  Bob       myTree insertRight  Tony       myTree insertRight  Steven       printTree myTree    Read more about it Here -This is a very simple implementation of a binary tree    This is a nice tutorial with questions in between

User · Answer

you don t need to have two classes  class Tree      val   None     left   None     right   None      def   init   self  val           self val   val       def insert self  val           if self val is not None              if val  lt  self val                  if self left is not None                      self left insert val                  else                      self left   Tree val              elif val  gt  self val                  if self right is not None                      self right insert val                  else                      self right   Tree val              else                  return         else              self val   val             print  new node added        def showTree self           if self left is not None              self left showTree           print self val  end                if self right is not None              self right showTree

User · Answer

Here is my simple recursive implementation of binary search tree     usr bin python  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 self  val           if self root is None              self root   Node val          else              self  add val  self root       def  add self  val  node           if val  lt  node v              if node l is not None                  self  add val  node l              else                  node l   Node val          else              if node r is not None                  self  add val  node r              else                  node r   Node val       def find self  val           if self root is not None              return self  find val  self root          else              return None      def  find self  val  node           if val    node v              return node         elif  val  lt  node v and node l is not None               self  find val  node l          elif  val  gt  node v and node r is not None               self  find val  node r       def deleteTree self             garbage collector will do this for us           self root   None      def printTree self           if self root is not None              self  printTree self root       def  printTree self  node           if node is not None              self  printTree node l              print str node v                     self  printTree node r         3   0     4     2      8 tree   Tree   tree add 3  tree add 4  tree add 0  tree add 8  tree add 2  tree printTree   print tree find 3  v  print tree find 10   tree deleteTree   tree printTree

User · Answer

Here is a simple solution which can be used to build a binary tree using a recursive approach to display the tree in order traversal has been used in the below code   class Node object        def   init   self           self left   None         self right   None         self value   None      property     def get value self           return self value       property     def get left self           return self left       property     def get right self           return self right       get left setter     def set left self  left node           self left   left node      get value setter     def set value self  value           self value   value      get right setter     def set right self  right node           self right   right node        def create tree self            node   Node    creating new node           x   input  Enter the node data -1 for null            if  x    str -1     for defining no child              return None          node set value    x  setting the value of the node          print  Enter the left child of     format  x            node set left   self create tree    setting the left subtree         print  Enter the right child of     format  x            node set right   self create tree    setting the right subtree           return  node      def pre order self  root           if root is not None              print root get value              self pre order root get left              self pre order root get right   if   name         main         node   Node       root node   node create tree       node pre order root node    Code taken from   Binary Tree in Python

User · Answer

usr bin python  class BinaryTree      def   init   self  left  right  data           self left   left         self right   right         self data   data       def pre order traversal root           print root data  end               if root left    None              pre order traversal root left           if root right    None              pre order traversal root right       def in order traversal root           if root left    None              in order traversal root left          print root data  end              if root right    None              in order traversal root right       def post order traversal root           if root left    None              post order traversal root left          if root right    None              post order traversal root right          print root data  end

[python] How to implement a binary tree?

Examples related to python

Examples related to algorithm

Examples related to search

Examples related to data-structures

Examples related to binary-tree