Hi! If you are thinking where have you arrived and have no clue of whats going on then visit this page.

Here is the lecture on general trees and binary trees by Prof Naveen Garg.

Some very important properties of a binary tree assuming that the height of the tree is h are:

1. The maximum number of nodes at each level of a binary tree is: 2^{l} where l is the level number.

2. The number of nodes **n** in a full binary tree are: **2 ^{h+1}-1**

This is because a binary tree of height h has h levels. So we add the number of nodes at each level

(2

^{0}+2

^{1}+2

^{2}…2

^{h})

3. The number of leaf nodes in a full binary tree is: 2^{h}

Here is the python implementation of a binary tree:

class BinaryTree: #binary tree constructor def __init__(self, root): self.root = root self.leftChild = None #initializing left child of a binary tree self.rightChild = None #initializing right child of a binary tree #method for setting the root of a binary tree def setRoot(self, root): self.root = root #method for getting the root of a binary tree def getRoot(self): return self.root #method for getting the left child of the binary tree def getLeftChild(self): return self.leftChild #method for getting the right child of the binary tree def getRightChild(self): return self.rightChild #method for inserting the left child of the binary tree def insertLeftChild(self, newNode): if self.leftChild == None: self.leftChild = BinaryTree(newNode) else: t = BinaryTree(newNode) t.leftChild = self.leftChild self.leftChild = t #method for inserting the right child of the binary tree def insertRightChild(self, newNode): if self.rightChild == None: self.rightChild = BinaryTree(newNode) else: t = BinaryTree(newNode) t.rightChild = self.rightChild self.rightChild = t

Advertisements

Pingback: Data Structures and Algorithms | codeatsociallywired