1.1 Concept and Terminologies 1.2 Types of Binary trees - Binary tree, skewed tree, strictly binary tree, full binary tree, complete binary tree, expression tree, binary search tree, Heap 1.3 Representation – Static and Dynamic 1.4 Implementation and Operations on Binary Search Tree - Create, Insert, Delete, Search, Tree traversals– preorder, inorder, postorder ( recursive implementation), Level-order traversal using queue, Counting leaf, non-leaf and total nodes, Copy, Mirror. 1.5 Applications of trees 1.5.1 Heap sort, implementation 1.5.2 Introduction to Greedy strategy, Huffman encoding (implementation using priority queue)

Become More Then A coder | Learn & Start Coding Now.

1.2 Types of Binary Trees:

- Binary Tree: A tree data structure in which each node has at most two children, left and right.

- Skewed Tree: A binary tree in which all nodes have only one child either to the left or right side.

- Strictly Binary Tree: A binary tree in which every node has either zero or two children.

- Full Binary Tree: A binary tree in which every node has either zero or two children and all leaves are at the same level.

- Complete Binary Tree: A binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

- Expression Tree: A binary tree used to represent mathematical expressions in which the operands are the leaves and the operators are the internal nodes.

- Binary Search Tree: A binary tree in which the left subtree of a node contains only nodes with keys less than the node's key, and the right subtree contains only nodes with keys greater than the node's key.

- Heap: A binary tree used to implement priority queues.

1.3 Representation:

- Static Representation: The tree is represented using an array or a linked list. It is easy to implement but the size of the tree is fixed.

- Dynamic Representation: The tree is represented using pointers. It is flexible but requires more memory.

1.4 Implementation and Operations on Binary Search Tree:

- Create: Create an empty binary search tree.

- Insert: Insert a node with a given key into the binary search tree.

- Delete: Delete a node with a given key from the binary search tree.

- Search: Search for a node with a given key in the binary search tree.

- Tree Traversals: Preorder, inorder, and postorder traversals can be done recursively.

- Level-Order Traversal: Traversal of the tree level by level using a queue.

- Counting Nodes: Count the number of leaf nodes, non-leaf nodes, and total nodes in the binary search tree.

- Copy: Create a copy of the binary search tree.

- Mirror: Create a mirror image of the binary search tree.

1.5 Applications of Trees:

- Heap Sort: A sorting algorithm that uses a heap data structure to sort an array.

- Greedy Strategy: A problem-solving approach that makes locally optimal choices at each step with the hope of finding a global optimum. Trees can be used to implement greedy algorithms.

- Huffman Encoding: A lossless data compression algorithm that uses a variable-length code table to compress data. It can be implemented using a priority queue which is typically implemented using a heap.