Trees

Definition :

The trees is a data structure that is used to representy hirerachical data. Something that is not possible in linear structures.

the top is the root and the children are called nodes. the nodes without any children are called leaves.

To iterate over all the nodes of a tree data structure there are two solutions :

• Breadth-level traversal : to check the tree by level.
• depth-first traversal : we check all the children of a node before moving to the next

Types of tree structure

Thanks to the parent-child relation, the tree structure is widly used for searching and sorting operations. It is considered to be one of the most powerful and advanced data structures.

Tree is not a linear data structure. It can be represented by various linear data structres such as arrays, linkedlists, classes or other types of data.

general tree :

A general tree has no condition on the number of children it can have. It is a super-set for all the other types of trees.

binary tree :

This tree has a condition/ constraint. Each node can only have two children. It is widly used thanks to this constraint. Indeed when we add conditions to data structures we discover new uses for them , for example when we add constraints to binary trees : Binary Search Tree, AVL, RBT

Binary search tree :

In BST the value of the left node most be smaller or equal to the parent node. This property makes BST suitable for sorting and searching.

One of the properties of a binary tree is the height :

Tree traversal :

There are three ways to traverse a tree :

• in order traversal : left, root and right
• pre order traversal : root, left and tight
• post order traversal : right, root, left

Here is a declaration of a binary search tree :

Here is a in order traversal :

For example while searching for an element we go through one branch of each node (according to its value). When searching for an element in a BST, the maximum time complexity is equal to number of node (n) of the binary tree and the minimum is log(n).

Important : we don't insert duplicate in a binary tree

A drawback of the BST is : The form of BST depends on the way we insert data. For n number of elements in the BST there are n! possible forms it can have With BST we can either have a maximum height tree or a minimum one (depends of how we insert data). We would like to have a minmum hight tree every time. To get this emprouvment we use AVL trees that result from rotating nodes in a classical BST.

AVL Tree (Alderson-Veski and Landis) :

AVL is a self balanced tree, resulting from rotating BST nodes. To rotate a BST, we first calculate a balance factor, it is calculated like this : ** Balance Factor = height of left subtree - hight of right subtree ** if BF's value is within {-1,0,1} this means that the tree is perfecty balanced.

For example here for the first node we have :

BF = 3 - 3 = 0 => balanced

For the second node we have :

BF = 2 - 0 = 2 => Unballanced

Method to three nodes :

1- LL imballance :

The first node is imbalanced from the left (we can know which side is heavier with the sign, '-' for right and '+' for the left). We will do a LL rotation like this :

now it is balanced

2- LR imballance :

We have a Left-Right imballance. we will perform this rotation :

Which will result in a LL imbalance

to get

3- RR imballance :

to have

3- RL imballance :

to haver a RR imbalance

And finaly

Methods to balance multiple trees :

LL and RR rotations :

If we have a BST like this that needs a LL rotation

It becomes like this :

LR and RL rotations :

it becomes like this

Red and Black tree :

another way to keep trees balanced. Here are its main conditions :

• Nodes be either black or red
• If a node is red then its children are black
• The root node and the NIL(element after the leaves) are always black
• All the pathes from a node to its descendent contain the same number of black nodes

This results to :

• We 1 need one more unit of storage to keep the color of the node
• The longuest path is < or = to 2 times the shortest path

The max time complexity for search, insert and delete is o(log(n)). But the space complexity is o(n) as we need to keep the color of every node

N-ary tree :

It is a tree where each node can have 0 to N children.

Tries/ digital trees :

https://www.youtube.com/watch?v=kMt9Y5fv4Ug&ab_channel=GoogleStudents + https://drstearns.github.io/tutorials/trie/ A type of tree that keeps the position of the elements within the "trie". It is usually used with stings. For example to store the words "ear, earl, earls, eat, eaten" the trie will look like this :

For example on many social media systems, you can refer to other users in your posts. As soon as you start typing a name, you often get a list of possible matches. The system might have millions of users, but it's able to show you suggestions as quickly as you can type.

This data structure is very efficient for search and retrieve operations. But takes o(n) complexity to do an insertion. It should be used to set up dictionaries.

A trie stores elements with a key and a value, it is like a BST with Maps in it. The key and value couple are called an entry. The value can have be wathever type we want. We can even have a map with a key and a non existing value (equivalent to a BST of sets).

declaration of trie data structure :

public class TrieNode {
    private HashMap<Character, TrieNode> children;
    private String content;
    private boolean isWord;
    
   // ...
}

The algorithme that adds a new entry to the Trie :

• let current node = root node
• for each letter in the key
  • find the child node of current node associated with that letter
  • if there is no child node associated with that letter, create a new node and add it to current node as a child associated with the letter
  • set current node = child node
• add value to current node

The algorithme of inserting a node is : (o of n complexity)

• Set a current node as a root node
• Set the current letter as the first letter of the word
• If the current node has already an existing reference to the current letter (through one of the elements in the “children” field), then set current node to that
  referenced node. Otherwise, create a new node, set the letter equal to the current letter, and also initialize current node to this new node
• Repeat step 3 until the key is traversed

Important notes:

• except tries, all the other tree types can only store primary int variables. As it cannot do a comparing operation between non primary types.

Exercices :

1- equal trees : https://leetcode.com/problems/same-tree/

In the beguining I had this solution :

But I didn't know how to get out of the loop. That's when I found this great solution :

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q ==null){return true;}
        if(p == null || q ==null){return false;}
        if(p.val != q.val){return false;}
        
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }

2- is a BST : https://www.hackerrank.com/challenges/ctci-is-binary-search-tree/

Same as the one I did before(you can find my solition in the repo). The solution is to use recursion with the '&&' operator.

3- Tries :

Indice : https://www.baeldung.com/trie-java