Skip to main content

Trees

Concept#

Tree is a data structure very similar to a tree that you see in the real world. It is a non-linear data structure as compared to array and linked list, heap as you have studied is a tree based data structure. So, what is the structure of a tree? How is it implemented? What are the advantages of a nonlinear tree data structure? Answer to all of these you will find only if read on.

Tree Traversal#

By now you know about a tree and its basic structure, here is a basic recursion based tree traversal technique that you ought to know to be able to solve more complex tree problems.

Do It Yourself : The recursive approach to tree traversals is easy but now that you know what tree traversal is, can you write an iterative approach for the same? Verify Your Answer

Different Types of Tree#

There are variations of tree, each having their own importance and applications, the basic variations have been discussed here, these variations have their own distinct properties that often are critical observation points to solve problems, for example, a balanced binary tree height is always logn, that makes it a useful data structure in situations where you cannot afford the height of the tree becoming more than logn where n is the number of nodes in the tree. It is recommended that you know and remember the distinct properties of each type of tree so that you are better equipped to solve more challenging problems.

Binary Tree#

It is a type of tree where any node in the tree can only have at max 2 child nodes.

Binary Search Tree#

Does the term "Binary Search" ring a bell? Binary Search Tree is exactly what it sounds, binary search applied on a tree, but if you are wondering how is that possible, we have found a good resource for you to learn from.

Balanced Tree#

The basic and most important property of a balanced tree is that the height is always logn where n is the number of nodes in the tree. Here you will learn only the basics of balanced tree, the implementation of a balanced tree such as AVL Tree, Red-Black Tree etc is an advanced level topic and you will learn about them later.

Q: What makes a self balancing BST the appropriate data structure for implementing maps and sets?

Q: How does a BST compare with Hash Table? What are the advantages of one over the other?

From your basic understanding of the two topics you should be easily able to answer this question. Here are a few points you should focus on if you are not, time complexity of basic insert, search, delete operations, the fundamental properties of the two data structures. Also go through the complete comparison of the two, this will help deepen your understanding. BST Vs Hash Table

Least Common Ancestor#

Finding LCA or the Least Common Ancestor is an intermediate step to solving more challenging and difficult tree problems, you are going to learn the different approaches to finding the LCA. You must be asking what is LCA? Once you read the following articles not only will you be able to answer this question but also know the optimised approach to finding LCA in O(logn) which is super useful and mind boggling, so what are you waiting for, go ahead and start reading.

Tree Flattening#

The concept of tree flattening is very interesting, representing a tree efficiently as an array. Euler Tour of trees is a general approach for tree flattening that has many applications. What is an euler tour of a tree? What are the advantages of tree flattening? To know the answers to these questions you have to but read on, you better get back to reading.

Segment Tree#

Segment Tree is one of the popular tree based data structure that lets you answer range queries efficiently. Suppose you are told to find the sum of all numbers from one index to another index in an array, then your basic implementation will have a time complexity of O(n), but after building a segment tree from the array, you can answer this query efficiently in O(logn). Caught your interest, didn’t it? Segment Tree is a super useful tool to have at your disposal and pretty easy to understand and build. So what is a segment tree? How does it help you in answering range queries? What kind of range queries can it answer? How can you implement it? Spend your time reading carefully and understanding the basic concepts of segment tree from these great articles. Post reading you should be able to answer the questions on your own.

Practice and Learn#

To take your understanding of segment tree to next level, practice and learn some the common problem patterns that can be solved using segment tree. Read this awesome tutorial on codeforces segment tree part 1 and part 2.

Least Common Ancestor Using RMQ#

Here you will learn another approach to finding least common ancestor using euler tour and segment tree. Already told you that they are very useful data structures available at your disposal.