yoti1412/binary_trees

Project: 0x1D. C - Binary trees

Resources

Read or watch:

• Binary tree
• Data Structure and Algorithms - Tree
• Tree Traversal
• Binary Search Tree
• Data structures: Binary Tree

Learning Objectives

General

• What is a binary tree
• What is the difference between a binary tree and a Binary Search Tree
• What is the possible gain in terms of time complexity compared to linked lists
• What are the depth, the height, the size of a binary tree
• What are the different traversal methods to go through a binary tree
• What is a complete, a full, a perfect, a balanced binary tree

Table of Contents

• Binary Trees
• Difference Between Binary Tree and Binary Search Tree
• Time Complexity Gain Compared to Linked Lists
• Binary Tree Properties
• Traversal Methods
• Types of Binary Trees

Binary Trees

A binary tree is a data structure in which each node has at most two child nodes, referred to as the left child and the right child.

Difference Between Binary Tree and Binary Search Tree

A Binary Search Tree (BST) is a specific type of binary tree that maintains a certain ordering property. In a BST, the left subtree of a node contains only nodes with values less than the node's value, and the right subtree contains only nodes with values greater than the node's value.

Time Complexity Gain Compared to Linked Lists

Binary trees can offer significant time complexity improvements over linked lists, especially for certain operations. For example, operations like searching, insertion, and deletion in a binary tree can have a time complexity of O(log n) on average, whereas in a linked list, these operations typically have a time complexity of O(n).

Binary Tree Properties

• Depth: The depth of a node in a binary tree is the distance from the root node to that node.
• Height: The height of a binary tree is the maximum depth among all nodes in the tree.
• Size: The size of a binary tree is the total number of nodes in the tree.

Traversal Methods

There are several methods to traverse a binary tree:

• In-order Traversal: Visit the left subtree, then the current node, and finally the right subtree.
• Pre-order Traversal: Visit the current node, then the left subtree, and finally the right subtree.
• Post-order Traversal: Visit the left subtree, then the right subtree, and finally the current node.
• Level-order Traversal: Visit nodes level by level, from left to right.

Types of Binary Trees

• Complete Binary Tree: A binary tree in which all levels are completely filled, except possibly the last level, which is filled from left to right.
• Full Binary Tree: A binary tree in which every node has either 0 or 2 children.
• Perfect Binary Tree: A binary tree in which all internal nodes have exactly two children, and all leaf nodes are at the same level.
• Balanced Binary Tree: A binary tree in which the height of the left and right subtrees of any node differs by at most one.