Deepak Soundappan - Binary Trees

Trees Binary trees are basically like a normal tree, a tree has branches and each branch can be connected to more branch. In the end there are leaves. You can imagine the same to be a form of a tree

Node is like a Branching Point in tree which actually is the heart of the data store in a tree. Any node will contain value which could be any type of data_type like, int, string or object or list of objects. Then there are the pointers to the other node from the current node.

A binary tree is a structure where there are only 2 branches to any node namely the left and right node.

Common use cases of using trees are Indexes in Database, Product Catalog, Expressions for RegEx, Code compilation etc.

Sample Code for 2 common type of trees are given below:

Sorted Binary Tree It is special binary tree, where the values in left are always lesser that the right end. It can be helpful in building databases indexes. It takes approximately O(log(N)) times for any data insert as the entire tree need not be searched through.

Generic Binary Tree Here the data is always inserted in the breadth first search (BFS) mode. Here the data is always inserted in the order in which data comes. It will take approximately O(N) time to do any insert.

Sorted Binary Tree: Performing Node Addition

Thanks @Noobcoder for your video on the visualization to insert binary tree.

Sorted Binary Tree: Performing Node deletion: Video to be added

Main Some basic processes that should be there in any linked list are

Checking length
Inserting node
Removing existing node
Printing the tree

3 important methods of traversing the binary tree are:

Pre Order (Root ➝ Left ➝ Right): The action of current node is incurred, followed by traversing the left node and then traversing the right node. Commonly used usecases:
1. Serialization / Deserialization of Trees: Serialization / Deserialization of Trees
2. Dependency resolution: Hierarchical UI / Menus / XML DOM Parsing: Useful when you want to save a tree structure to a file or send over a network.
In Order (Left ➝ Root ➝ Right): The traversing the left node occurred, followed by action in the current node finally followed by traversing the right node. Commonly used usecases:

Binary Search Tree (BST): Sorted Output: Retrieves elements in ascending order. Useful for reporting systems, leaderboard systems, or any system that needs sorted data.
Data export or printing: If data in a tree needs to be presented in logical order, like generating reports or invoices.
Post Order (Left ➝ Right ➝ Root): The traversing the left node and then traversal of the right node followed by action of current node is incurred. Commonly used usecases:
1. Deleting or freeing resources : Safely deletes or releases children before the parent (e.g., memory management, file cleanup).
2. Task execution where dependencies must be resolved before parent task (e.g., Airflow DAGs, CI/CD pipelines).

Page updated

Google Sites

Report abuse