A complete binary tree is a tree in which each level has all of its nodes.
To find the parent of any node in the tree, we can simply use Python’s integer division. Given that a node is at position n in the list, the parent is at position n//2.
The Heap Order Property
Binary Tree Applications
Parse trees can be used to represent real-world constructions like sentences or mathematical expressions.
Tree Traversals
preorder: In a preorder traversal, we visit the root node first, then recursively do a preorder traversal of the left subtree, followed by a recursive preorder traversal of the right subtree.
inorder: In an inorder traversal, we recursively do an inorder traversal on the left subtree, visit the root node, and finally do a recursive inorder traversal of the right subtree.
postorder: In a postorder traversal, we recursively do a postorder traversal of the left subtree and the right subtree followed by a visit to the root node.
Suppose that you wanted to read this book from front to back. The preorder traversal gives you exactly that ordering. Starting at the root of the tree (the Book node) we will follow the preorder traversal instructions. We recursively call preorder on the left child, in this case Chapter 1. We again recursively call preorder on the left child to get to Section 1.1. Since Section 1.1 has no children, we do not make any additional recursive calls. When we are finished with Section 1.1, we move up the tree to Chapter 1.
# function
def preorder(tree):
if tree:
print(tree.get_root_val())
preorder(tree.get_left_child())
preorder(tree.get_right_child())
# method
def preorder(self):
print(self.key)
if self.left_child:
self.left.preorder()
if self.right_child:
self.right.preorder()
# function
def postorder(tree):
if tree != None:
postorder(tree.get_left_child())
postorder(tree.get_right_child())
print(tree.get_root_val())
# function
def inorder(tree):
if tree != None:
inorder(tree.get_left_child())
print(tree.get_root_val())
inorder(tree.get_right_child())
Binary Tree and its traversal using python.
Lets take the below tree for example.
Inorder traversal
In order traversal means visiting first left, then root and then right.
So the traversal of above tree would be 4 2 5 1 3
Pre Order Traversal
In this traversal we first visit root, then left, then right
It will be something like this 1 2 4 5 3
Post Order traversal
Here we first visit left, then right and then root.
It will be something like this 4 5 2 3 1
These were the traversal now lets code it in python
So this is how you write the binary tree in Python.
Lets have a look at the script.
We made a class Node which represent the node of Binary tree. We initialize the node with data and left and right child as None.
When we add new child we simple use root.left or root.left.left to add a new child.
Now lets have a look at the traversal functions.
In all these functions we took advantage of recursion and passed the subtrees in the functions again to print in proper order. In Inorder function, we first pass the left subtree to Inorder then print the node and then pass the right subtree. Thus made left, root and right. Similarly we did for the other two.
Here we took a look into how to code binary Tree and its traversal using python.
Algorithms: Mirror a Binary tree using python
Lets take the below tree for example.
So we will be writing python code for changing the tree to its mirror.
Thus you can see the mirror trees inorder traversal. It was really simple we just traversed the tree and changed the right subtree with left and left subtree with right subtree.
Level order traversal of a binary tree.
Level order traversal means that we visit the nodes level by level. Like for below tree the level order traversal will be
Node class to make the nodes of binary search tree.
Then insert functions, what this function is doing is checking if the data is lesser than node then moves to left child else moves to right child and place it at the end.
Search function again works same as insert functions. The only difference is in this we are getting and telling if the data is present while in insert we are adding node to the true.
In order traversal to visit all the node. Do you know in order traversal of binary search tree is in sorted order.
Get min and Get max functions to get the minimum and maximum of the Binary Search Tree.
Delete I am leaving delete function for you. If you are stuck comment below and I will write a delete function for you.
Rosettacode.org
Procedural
from collections import namedtuple
from sys import stdout
Node = namedtuple('Node', 'data, left, right')
tree = Node(1,
Node(2,
Node(4,
Node(7, None, None),
None),
Node(5, None, None)),
Node(3,
Node(6,
Node(8, None, None),
Node(9, None, None)),
None))
def printwithspace(i):
stdout.write("%i " % i)
def preorder(node, visitor = printwithspace):
if node is not None:
visitor(node.data)
preorder(node.left, visitor)
preorder(node.right, visitor)
def inorder(node, visitor = printwithspace):
if node is not None:
inorder(node.left, visitor)
visitor(node.data)
inorder(node.right, visitor)
def postorder(node, visitor = printwithspace):
if node is not None:
postorder(node.left, visitor)
postorder(node.right, visitor)
visitor(node.data)
def levelorder(node, more=None, visitor = printwithspace):
if node is not None:
if more is None:
more = []
more += [node.left, node.right]
visitor(node.data)
if more:
levelorder(more[0], more[1:], visitor)
stdout.write(' preorder: ')
preorder(tree)
stdout.write('\n inorder: ')
inorder(tree)
stdout.write('\n postorder: ')
postorder(tree)
stdout.write('\nlevelorder: ')
levelorder(tree)
stdout.write('\n')
Subclasses a namedtuple adding traversal methods that apply a visitor function to data at nodes of the tree in order
from collections import namedtuple
from sys import stdout
class Node(namedtuple('Node', 'data, left, right')):
__slots__ = ()
def preorder(self, visitor):
if self is not None:
visitor(self.data)
Node.preorder(self.left, visitor)
Node.preorder(self.right, visitor)
def inorder(self, visitor):
if self is not None:
Node.inorder(self.left, visitor)
visitor(self.data)
Node.inorder(self.right, visitor)
def postorder(self, visitor):
if self is not None:
Node.postorder(self.left, visitor)
Node.postorder(self.right, visitor)
visitor(self.data)
def levelorder(self, visitor, more=None):
if self is not None:
if more is None:
more = []
more += [self.left, self.right]
visitor(self.data)
if more:
Node.levelorder(more[0], visitor, more[1:])
def printwithspace(i):
stdout.write("%i " % i)
tree = Node(1,
Node(2,
Node(4,
Node(7, None, None),
None),
Node(5, None, None)),
Node(3,
Node(6,
Node(8, None, None),
Node(9, None, None)),
None))
if __name__ == '__main__':
stdout.write(' preorder: ')
tree.preorder(printwithspace)
stdout.write('\n inorder: ')
tree.inorder(printwithspace)
stdout.write('\n postorder: ')
tree.postorder(printwithspace)
stdout.write('\nlevelorder: ')
tree.levelorder(printwithspace)
stdout.write('\n')
Output:
As above.
Python: Composition of pure (curried) functions
Currying by default is probably not particularly 'Pythonic', but it does work well with higher-order functions – giving us more flexibility in compositional structure. It also often protects us from over-proliferation of the slightly noisy lambda keyword. (See for example the use of the curried version of map in the code below).
The approach taken here is to focus on the evaluation of expressions, rather than the sequencing of procedures. To keep evaluation simple and easily rearranged, mutation is stripped back wherever possible, and 'pure' functions, with inputs and outputs but, ideally, with no side-effects (and no sensitivities to global variables) are the basic building-block.
Composing pure functions also works well with library-building and code reuse – the literature on functional programming (particularly in the ML / OCaml / Haskell tradition) is rich in reusable abstractions for our toolkit. Some of them have already been absorbed, with standard or adjusted names, into the Python itertools module. (See the itertools module preface, and the takewhile function below).
Here, for example, for the pre-, in- and post- orders, we can define a very general and reusable foldTree (a catamorphism over trees rather than lists) and just pass 3 different (rather simple) sequencing functions to it.
This level of abstraction and reuse brings real efficiencies – the short and easily-written foldTree, for example, doesn't just traverse and list contents in flexible orders - we can pass all kinds of things to it. For the sum of all the numbers in the tree, we could write:
foldTree(lambda x: lambda xs: x + sum(xs))(tree)
and for various other metrics, and the traversal sequences:
'''Tree traversals'''
from itertools import (chain, takewhile)
from functools import (reduce)
from operator import (mul)
# foldTree :: (a -> [b] -> b) -> Tree a -> b
def foldTree(f):
'''The catamorphism on trees.
A summary value derived by a depth-first fold.'''
def go(node):
return f(root(node))(
list(map(go, nest(node)))
)
return lambda tree: go(tree)
# levels :: Tree a -> [[a]]
def levels(tree):
'''A list of the nodes at each level of the tree.'''
map_ = curry(map)
return list(
map_(map_(root))(
takewhile(
bool,
iterate(concatMap(nest))(
[tree]
)
)
)
)
# preorder :: a -> [[a]] -> [a]
def preorder(x):
'''This node followed by the rest.'''
return lambda xs: [x] + concat(xs)
# inorder :: a -> [[a]] -> [a]
def inorder(x):
'''Descendants of any first child,
then this node, then the rest.'''
return lambda xs: (
xs[0] + [x] + concat(xs[1:]) if xs else [x]
)
# postorder :: a -> [[a]] -> [a]
def postorder(x):
'''Descendants first, then this node.'''
return lambda xs: concat(xs) + [x]
# levelorder :: Tree a -> [a]
def levelorder(tree):
'''Top-down concatenation of this node
with the rows below.'''
return concat(levels(tree))
# treeSum :: Tree Int -> Int
def treeSum(x):
'''This node's value + the sum of its descendants.'''
return lambda xs: x + sum(xs)
# treeSum :: Tree Int -> Int
def treeProduct(x):
'''This node's value * the product of its descendants.'''
return lambda xs: x * numericProduct(xs)
# treeMax :: Tree Int -> Int
def treeMax(x):
'''Maximum value of this node and any descendants.'''
return lambda xs: max([x] + xs)
# treeMin :: Tree Int -> Int
def treeMin(x):
'''Minimum value of this node and any descendants.'''
return lambda xs: min([x] + xs)
# nodeCount :: Tree a -> Int
def nodeCount(_):
'''One more than the total number of descendants.'''
return lambda xs: 1 + sum(xs)
# treeWidth :: Tree a -> Int
def treeWidth(_):
'''Sum of widths of any children, or a minimum of 1.'''
return lambda xs: sum(xs) if xs else 1
# treeDepth :: Tree a -> Int
def treeDepth(_):
'''One more than that of the deepest child.'''
return lambda xs: 1 + (max(xs) if xs else 0)
# TEST ----------------------------------------------------
# main :: IO ()
def main():
'''Test'''
# tree :: Tree Int
tree = Node(1)([
Node(2)([
Node(4)([
Node(7)([])
]),
Node(5)([])
]),
Node(3)([
Node(6)([
Node(8)([]),
Node(9)([])
])
])
])
for f in [preorder, inorder, postorder, levelorder,
treeSum, treeProduct, treeMin, treeMax,
nodeCount, treeWidth, treeDepth]:
s = f.__name__
print(
s.rjust(12, ' ') + ':',
(foldTree(f) if 'levelorder' != s else f)(
tree
)
)
# GENERIC -------------------------------------------------
# Node :: a -> [Tree a] -> Tree a
def Node(v):
'''Contructor for a Tree node which connects a
value of some kind to a list of zero or
more child trees.'''
return lambda xs: {'type': 'Node', 'root': v, 'nest': xs}
# nest :: Tree a -> [Tree a]
def nest(tree):
'''Accessor function for children of tree node'''
return tree['nest'] if 'nest' in tree else None
# root :: Dict -> a
def root(tree):
'''Accessor function for data of tree node'''
return tree['root'] if 'root' in tree else None
# concat :: [[a]] -> [a]
# concat :: [String] -> String
def concat(xxs):
'''The concatenation of all the elements in a list.'''
xs = list(chain.from_iterable(xxs))
unit = '' if isinstance(xs, str) else []
return unit if not xs else (
''.join(xs) if isinstance(xs[0], str) else xs
)
# concatMap :: (a -> [b]) -> [a] -> [b]
def concatMap(f):
'''Concatenated list over which a function has been mapped.
The list monad can be derived by using a function f which
wraps its output a in list,
(using an empty list to represent computational failure).'''
return lambda xs: list(
chain.from_iterable(
map(f, xs)
)
)
# curry :: ((a, b) -> c) -> a -> b -> c
def curry(f):
'''A curried function derived
from an uncurried function.'''
return lambda a: lambda b: f(a, b)
# iterate :: (a -> a) -> a -> Gen [a]
def iterate(f):
'''An infinite list of repeated applications of f to x.'''
def go(x):
v = x
while True:
yield v
v = f(v)
return lambda x: go(x)
# numericProduct :: [Num] -> Num
def numericProduct(xs):
'''The arithmetic product of all numbers in xs.'''
return reduce(mul, xs, 1)
if __name__ == '__main__':
main()
In a heap, for every node x with parent p, the key in p is smaller than or equal to the key in x.
are the tree where one node can have only two child and cannot have more than two. Traversal means visiting all the nodes of the Binary tree. There are three types of traversal.
Binary Tree and its traversal using python.
are the tree where one node can have only two child and cannot have more than two. Traversal means visiting all the nodes of the Binary tree.
Algorithms: Mirror a Binary tree using python
Level order traversal of a binary tree.
Back in the algorithms section with python we are going to see how we can code and its functionality in python. are binary tree where the left child is less than root and right child is greater than root. We will be performing insertion, searching, traversal, min and other functions. .Level order traversal of a binary tree.
