tree data structure - OpenGenus IQ: Computing Expertise & Legacy

Construct BST from pre-order traversal (using monotonic stack; no recursion)

This article discusses on a way in which, Binary Search Tree (BST) can be reconstructed when corresponding pre-order traversal of the tree is input, using a concept of monotonic stack.

Data Structures

Basics of R Tree

R-tree is an advanced height-balanced Tree Data Structure that is widely used in production for spatial problems (like geographical map operations). We have presented the need for R Tree along with the basics of R Tree

Problems on Binary Tree

Finding Diameter of a Tree using DFS

In this article, we will be discussing how to find the diameter of a tree or graph using Depth First Search (DFS).

Problems on Binary Tree

Diameter of a Binary Tree

In this problem, we are given input as the reference to the root of a binary tree. We need to find the diameter of the tree. We find the diameter using recursion and Depth First Search (DFS).

Problems on Binary Tree

Algorithm to find Level of each node from root node

In this article we will be discussing on how to find the level of each node in a graph, the algorithm that we will be using to find the level of each node is breadth first search.

Problems on Binary Tree

Counting subtrees where nodes sum to a specific value

We will learn about counting the subtrees in a binary tree whose nodes sum to a given value. We will be trying different methods to solve our problem We will solve it in O(N) time complexity and O(H) space complexity where N is number of nodes and H is the height of the tree.

Data Structures

Different Self Balancing Binary Trees

A self-balancing binary tree is any tree that automatically keeps its height small in the face of arbitrary insertions and deletions on the tree. We have explored different types like 2 3 tree, Red Black tree, AVL Tree, B Tree, AA Tree, Scapegoat Tree, Splay Tree, Treap and Weight Balanced Tree.

Data Structures

Introduction to 2-3 Trees

A 2-3 Tree is a tree data structure where every node with children has either two children and one data element or three children and two data elements. A node with 2 children is called a 2-NODE and a node with 3 children is called a 3-NODE.

Data Structures

Implementing a Binary Search Tree (BST) in C++

In this article, we have explained the idea of implementing Binary Search Tree (BST) from scratch in C++ including all basic operations like insertion, deletion and traversal.

Data Structures

Introduction to AA trees

AA trees were introduced by Arne Andersson in 1993 and hence the name AA. They are a type of balanced binary search trees. It was developed as a simpler alternative to Red Black trees.

Problems on Binary Tree

Implementing Binary tree in C++

In this article, we have explored how to implement Binary Tree Data Structure in C++ including all different operations like traversing, inserting and deleting. We have used Object Oriented Programming (OOP) concepts.

Data Structures

Space partitioning trees

Space partitioning trees are tree data structures that partition a N-dimensional data space into different components for specific tasks. Examples of Space partitioning trees include Binary Space Partitioning tree, Octree and many more.

Data Structures

Burkhard Keller Tree (BK Tree)

Burkhard Keller Tree (BK-Tree) is a Tree Data Structure that is used to find the near-matches to a String Query. It is used in several applications like spell correction and autocompletion.

Data Structures

Interval Trees: One step beyond BST

Interval tree is a variant of BST and is able to handle intervals in logarithmic time for search, insert and delete operations and is used in geometry.

Data Structures

Persistent Segment Tree

Our aim is to introduce persistency in segment trees but also ensure that the space and time complexity is not affected.

Data Structures

Rope: the Data Structure used by text editors to handle large strings

Rope data structure is widely used by software such as text editors like Sublime, email systems like Gmail and text buffers to handle large strings efficiently.

Data Structures

Count inversions in an array using Fenwick Tree

Fenwick tree is usually used for range query problems but it can be used to solve the problem of finding the number of inversions in an array efficiently.

Data Structures

Understanding Fenwick tree (Binary Indexed Tree) with Range product

Fenwick tree is a tree based data structure that is widely used to solve range query problems in logarithmic time O(log N) which would otherwise have taken linear time O(N). In this article, we have explained it in depth using the range product query problem.

Problems on Binary Tree

Learn how to traverse a Binary Tree (Inorder , Preorder , Postorder)

In this article we will learn three Depth first traversals namely inorder, preorder and postorder and their use. These three types of traversals generally used in different types of binary tree. In summary, Inorder: left, root, right; Preorder: root, left, right and Postorder: left, right, root

Problems on Binary Tree

Understand everything about Binary Search Tree

Binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers in a tree data structure. It can be used to search for the presence of a number in O(log(n)) time and a simple traversal gives the numbers in sorted order.

Data Structures

Fibonacci Heap

A Fibonacci heap is a heap data structure similar to the binomial heap. It uses Fibonacci numbers and also used to implement the priority queue element in Dijkstra’s shortest path algorithm which reduces the time complexity from O(m log n) to O(m + n log n)

Problems on Binary Tree

Binary Tree

A binary tree is a tree data structure in which each node has upto two children (that is a maximum of two children nodes), which are referred to as the left child and the right child. Implementation and applications of binary tree

Data Structures

Max Heap and Min Heap

A min heap is a heap where every single parent node, including the root, is less than or equal to the value of its children nodes. The most important property of a min heap is that the node with the smallest, or minimum value, will always be the root node. Max heap is similar

Data Structures

K Dimensional Tree / (K D Tree)

K Dimensional tree (or k-d tree) is a tree data structure that is used to represent points in a k-dimensional space. It is used for various applications like nearest point (in k-dimensional space), efficient storage of spatial data, range search. We implemented it in C++ and explained the operations

Data Structures

Octree data structure

Octree is a tree data structure where each internal node has 8 children. An octree is generally used to represent relation between objects in a 3-dimensional space. It is used in 3D computer graphics. Octrees are also used for nearest neighbor search which can be done easily in logarithmic time.