# Tree Data Structure and Initialization and Methods Python

Sun Jul 31 2022 00:30:11 GMT+0000 (Coordinated Universal Time)

```# //Lists are linear but trees are nonlinear
# //Often working with binary trees and specifically binary search trees

# //SL is techically a special case tree

# //Root: top node of tree
# //Child: node directly connected to another node when moving away from root
# //Parent: converse notion of child
# //Siblings: group of node with same parent
# //Leaf: node with no children
# //Edge: connection betweeen one node and another (often arrows)

# //Used for HTML DOM, network routing, abstract syntax trees, folder organization, AI, best possible move (decision tree)

# //We will focus on binary search tree (can only have at most 2 child nodes)
# //For each node, everything to left is smaller. Right >> bigger

class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

class BinarySearchTree:
def __init__(self):
self.root = None

def insert(self, value):
#creates new Node
new_node = Node(value)
#start at root
#if no root exists, root becomes new_node
if self.root == None:
self.root = new_node
return self

current = self.root

while True:
#to handle special case where value is same as current node
#you can return None or you can add a counter property
if value == current.value:
return None
#check to see if value is less than current
if value < current.value:
#check to see if there is node to left
#if not, add new_node to left
if current.left == None:
current.left = new_node
return self
#if there is node to left, move to that node and repeat
current = current.left
#check to see if value is greater than current
else:
#check to see if there is node to right
#if not, add new_node to right
if current.right == None:
current.right = new_node
return self
#if there is node to right, move to that node and repeat
current = current.right

#find() returns value while contains() returns boolean
#find will point to entire node
def find(self, value):
#check to see if there is root and if not, we are done!
if self.root == None:
return False
current = self.root
found = False

#if value is less than current
if value < current.value:
#check to see if there is node to left
#if there is, move to that node and repeat
current = current.left
#if not, we ar edone because current will no longer exist
#if value is greater than current
elif value > current.value:
#check to see if there is node to right
#if there is, move to that node and repeat
current = current.right
#if not, we are done because current will no longer exist
else:
found = True

return None
return current

def contains(self, value):
if self.root == None:
return False
current = self.root
found = False

if value < current.value:
current = current.left
elif value > current.value:
current = current.right
else:
return True
return False

t = BinarySearchTree()
t.insert(3)
t.insert(5)
t.insert(2)
t.insert(-1)
t.insert(6)
t.find(6)
t.contains(6)

# // Insertion and Search: O(log N) VERY GOOD
# // Not guaranteed if BST is a one sided tree (choose a different root)

# //      10
# //   5     13
# // 2  7  11  16

# // tree = BinarySearchTree()
# // tree.insert(10)
# // tree.insert(5)
# // tree.insert(13)
# // tree.insert(11)
# // tree.insert(2)
# // tree.insert(16)
# // tree.insert(7)
# // tree.find(7) >> will point to node with 7
# // tree.contains(6) >> False

# //Primitive way of making Tree before insert()
# // tree = BinarySearchTree()
# // tree.root = Node(10)
# // tree.root.right = Node(15)
# // tree.root.left = Node(7)
# // tree.root.left.right = Node(9)

```
content_copyCOPY

Udemy