Related Topics
Data Structure
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.parent = None
self.color = 1
class RedBlackTree:
def __init__(self):
self.nil = Node(0)
self.nil.color = 0
self.root = self.nil
def left_rotate(self, x):
y = x.right
x.right = y.left
if y.left != self.nil:
y.left.parent = x
y.parent = x.parent
if x.parent == self.nil:
self.root = y
elif x == x.parent.left:
x.parent.left = y
else:
x.parent.right = y
y.left = x
x.parent = y
def right_rotate(self, x):
y = x.left
x.left = y.right
if y.right != self.nil:
y.right.parent = x
y.parent = x.parent
if x.parent == self.nil:
self.root = y
elif x == x.parent.right:
x.parent.right = y
else:
x.parent.left = y
y.right = x
x.parent = y
def insert(self, key):
node = Node(key)
node.parent = None
node.key = key
node.left = self.nil
node.right = self.nil
node.color = 1
y = None
x = self.root
while x != self.nil:
y = x
if node.key < x.key:
x = x.left
else:
x = x.right
node.parent = y
if y == None:
self.root = node
elif node.key < y.key:
y.left = node
else:
y.right = node
if node.parent == None:
node.color = 0
return
if node.parent.parent == None:
return
self.fix_insert(node)
def delete(self, key):
z = self.search(key)
if z == self.nil:
return
self.delete_node(z)
def find_min(self, node):
while node.left != self.nil:
node = node.left
return node
def delete_node(self, node):
y = node
y_original_color = y.color
if node.left == self.nil:
x = node.right
self.transplant(node, node.right)
elif node.right == self.nil:
x = node.left
self.transplant(node, node.left)
else:
y = self.find_min(node.right)
y_original_color = y.color
x = y.right
if y.parent == node:
x.parent = y
else:
self.transplant(y, y.right)
y.right = node.right
y.right.parent = y
self.transplant(node, y)
y.left = node.left
y.left.parent = y
y.color = node.color
if y_original_color == 0:
self.fix_delete(x)
def transplant(self, u, v):
if u.parent == None:
self.root = v
A A
/ \ / \
B C B C
/ \ / / \ /
D E F D E F
The left tree is a full binary tree, as every node has either zero or two children. The right tree is a complete binary tree, as every level is completely filled, except for the last level which is filled from left to right. Note that the right tree is not a full binary tree because node C has only one child.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def find_lca(root, p, q):
# If root is NULL or equal to either of the two nodes, return the root
if root is None or root.val == p.val or root.val == q.val:
return root
# Recursively search for the left and right subtrees of the root for the two nodes
left_lca = find_lca(root.left, p, q)
right_lca = find_lca(root.right, p, q)
# If the two nodes are found in different subtrees of the root, return the root since it is the LCA
if left_lca and right_lca:
return root
# If the two nodes are found in the same subtree of the root, recursively search that subtree for the LCA
return left_lca if left_lca else right_lca
In this implementation, root is the root node of the binary tree, p and q are the nodes for which we want to find the LCA. The function returns the LCA of p and q. If either p or q is not present in the tree, it returns None.
def bfs(root):
queue = [root]
while queue:
node = queue.pop(0)
print(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
DFS (in-order):
def dfs_inorder(node):
if node:
dfs_inorder(node.left)
print(node.val)
dfs_inorder(node.right)
DFS (pre-order):
def dfs_preorder(node):
if node:
print(node.val)
dfs_preorder(node.left)
dfs_preorder(node.right)
DFS (post-order):
def dfs_postorder(node):
if node:
dfs_postorder(node.left)
dfs_postorder(node.right)
print(node.val)
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def mirror_tree(root):
if root is None:
return
else:
mirror_tree(root.left)
mirror_tree(root.right)
temp = root.left
root.left = root.right
root.right = temp
In this implementation, we first check if the root is None. If it is, we return. Otherwise, we recursively call mirror_tree on the left and right subtrees of the root, and then swap their positions using a temporary variable. This effectively mirrors the tree. We can call this function on the root node of our binary tree to obtain its mirror image.
A
/ \
B C
/ \ / \
D E F G
In contrast, a complete binary tree is a binary tree where all levels are completely filled, except possibly the last level, which is filled from left to right. So, a complete binary tree may have some internal nodes with only one child.
For example, the following is a complete binary tree, but not a perfect binary tree:
A
/ \
B C
/ \ /
D E F
Popular Category
Topics for You
Go through our study material. Your Job is awaiting.