Scribd
Upload
211 views3 pages

Trees Complete Notes

This document provides comprehensive notes on tree data structures, covering basic concepts, types of trees, and various tree traversal methods. It includes detailed explanations and sample code for Binary Search Trees, AVL Trees, and operations such as insertion, deletion, and finding the lowest common ancestor. Additionally, it discusses applications of trees and methods for checking balance and creating mirror trees.

Uploaded by

Pavani Ankala
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
211 views3 pages

Trees Complete Notes

This document provides comprehensive notes on tree data structures, covering basic concepts, types of trees, and various tree traversal methods. It includes detailed explanations and sample code for Binary Search Trees, AVL Trees, and operations such as insertion, deletion, and finding the lowest common ancestor. Additionally, it discusses applications of trees and methods for checking balance and creating mirror trees.

Uploaded by

Pavani Ankala
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Tree Data Structures - Complete Notes

1. Basic Concepts

Tree: A hierarchical structure with root and subtrees.

Node: Contains data and references.

Edge: Link between nodes.

Root, Leaf, Parent, Child, Sibling, Height, Depth, Degree.

2. Types of Trees

- Binary Tree

- Full, Perfect, Complete, Balanced Binary Trees

- Binary Search Tree (BST)

- AVL Tree

- Red-Black Tree

- B-Tree

- Trie

3. Tree Traversals

Inorder (LNR), Preorder (NLR), Postorder (LRN), Level Order (BFS).

Sample Code:

def inorder(root):

if root:

inorder(root.left)

print(root.data)

inorder(root.right)

4. Binary Search Tree (BST)

Insert, Delete, Search.

Sample Insert:

def insert(root, key):

if not root: return Node(key)

if key < root.data:


Tree Data Structures - Complete Notes

root.left = insert(root.left, key)

else:

root.right = insert(root.right, key)

return root

5. Height, Count, Leaves

def height(root): return 0 if not root else 1 + max(height(root.left), height(root.right))

def count_nodes(root): return 0 if not root else 1 + count_nodes(root.left) + count_nodes(root.right)

def count_leaves(root): return 1 if root and not root.left and not root.right else count_leaves(root.left) +

count_leaves(root.right)

6. Lowest Common Ancestor (LCA)

def lca(root, n1, n2):

if not root: return None

if root.data == n1 or root.data == n2: return root

left = lca(root.left, n1, n2)

right = lca(root.right, n1, n2)

return root if left and right else left or right

7. Balanced Tree Check

def is_balanced(root):

def check(root):

if not root: return 0

lh = check(root.left)

rh = check(root.right)

if abs(lh - rh) > 1: return -1

return 1 + max(lh, rh)

return check(root) != -1

8. Mirror Tree
Tree Data Structures - Complete Notes

def mirror(root):

if root:

root.left, root.right = root.right, root.left

mirror(root.left)

mirror(root.right)

9. Applications

- Expression Trees

- Decision Trees

- Tries

- Heaps

- Segment Trees

10. AVL Tree (Self-Balancing BST)

AVL Tree maintains balance using rotations.

Balance Factor = height(left) - height(right)

If |BF| > 1, apply:

- Left Rotate

- Right Rotate

- Left-Right Rotate

- Right-Left Rotate

Sample Rotation:

def right_rotate(y):

x = y.left

T2 = x.right

x.right = y

y.left = T2

return x

You might also like