b001ean's blog

By b001ean, 3 years ago, In English

Hey Guys ! This is my first education blog , now in Codeforces, acc to me , we don't use so much pointers so like if there is some tree question then we would directly convert it into graph or use graph algos to do it. So I studied on trees for like 3-4 days and I really want to share my knowledge with you all genius and smart people.

PS: I just new to this , if I did any mistake then please correct me :)

POINTER TO POINTER METHOD IN TREES

Now I realized that many my friends do questions in return type of recursive function like if you are inserting or deleting the node or changing the edges then you would use return type as when we send this argument node * root then we are not actually sending root , we are sending the copy of root or maybe you can say that we are sending the another pointer which is pointing to the same node which the root was pointing then I thought it would be easy to do questions if we actual send the real root , why do we have to send copy , if we able to send the real root then we could able to do all questions in void , so no need to return type so for that use

node* &root so by this we could able to send the real root or you can say we have made a pointer which is pointing the root pointer/ storing address of root pointer.

BST

Recursive Part

Now I used GeeksforGeeks for this (those 20 questions on BST trees were awesome!)

1) Print Postorder traversal from the given pre and inorder traversal

Root is always the first element in pre-order transversal and it is last element in post-order traversal Now the challenging thing is that to find the boundaries of the left and right subtree so in INORDER all elements left to the root are left elements and right to the root are right elements Now,in pre , all elements after the index of the root are elements of right subtree and all elements before the index of the root [including the index of root in inorder but excluding the first element of pre order] are elements of the left subtree

Now let — Inorder be : DBEAFC — preorder be: ABDECF

Now A is root so DBE in inorder will be left subtree so BDE is also left sub tree from pre-order

Now we are here — Inorder : DBE — Preorder : BDE

now the root is B (as first element of the preorder is root so all left elements before B are it's left element now then

  • Inorder :D
  • pre-order :D

so single element so print it [as we are at the left leave node now] so now B's right element would be called

  • Inorder :E
  • preorder :E

now single element print it Now we traverse came back to B then print B now DEB is printed till now same do for FC in order as they are right subtree should I explain the FC part also ? okk

so — Inorder :FC — pre-oder :CF

now C is root then no right element and only F left element , so now DEBFC now we traversed back to A again so final print is DEBFCA

Notice some imp point: You see that in this recursion we made root every node first A then B->D->E->C->F so is this same order in pre-order???

ohh yes! it is !

so we will use this thing to implement in our code

CODE

Below is the implementation.

Just try urself!first :)

CODE

Now this is o(n^2) algorithm

Let's optimize it to o(n) algo As we know that in BST every node is Unique value so why we are doing searching , we can store all values in MAP and after that then we can find the element in o(1) time

so instead of making search function use map

 for (int i = 0; i < n; i++)m[in[i]] = i; // stored all indexes of the unique values

2) Tree from pre-order and Inorder Traversal

Hint: use previous algo to do it :)

CODE

code

[when PreIndex reach Inorder[preorder[0]] then left subtree would be formed of main root and from Inorder[Preorder[0]]+1 right subtree will start forming ]

2.1) Tree from post-order and In-order

Now , for like

Inorder : 42513 Post-order : 45231

and actual tree is

   
Now notice one thing root is always at end so we will able to find the root from the end of the post-order and end-1 of postorder contains the root of right subtree, so as In pre-order we used to go from 0 to n-1 as we used to solve left first then right as in pre-order first left comes after root [remember center-left-right] Now here before root, right comes[left-right-center/root] so we will go from n-1 to 0 and solve first right then left!

CODE

CODE

3)Finding the kth smallest element

Hint
Main solution

vector v;
void inorder(TreeNode* &root, int k)
{
if(root==NULL) return;
inorder(root->left, k);
v.push_back(root->val);
if(v.size()>=k) return;
inorder(root->right, k);
}

4) 2 sum Binary Tree

Given a binary search tree T, where each node contains a positive integer, and an integer K, we have to find whether or not there exist two different nodes A and B such that A.value + B.value = K.

PLEASE TRY FIRST THEN SEE THE CODE :)

Hint1
Hint2
Main solution

CODE

CODE

5)How to find that is the Traversal is Valid or not?

Now like we have given a preorder traversal A, of a Binary Search Tree. Find if it is a valid preorder traversal of a BST.

:

Hint0
Hint1
Hint2

code

{note : here we are traversing on pre-order}

Code

6)Convert sorted Array to Balanced BST

:

Solution

7)Recover Binary Search

Two elements of a binary search tree (BST) are swapped by mistake. we have to tell the 2 values swapping which the tree will be restored.

Method

8)Inorder Traversal of Cartesian Tree

Cartesian tree : is a heap ordered binary tree, where the root is greater than all the elements in the subtree

Hint
Implementation

NON recursive part in stacks

Implementing Traversals using Stacks

In-order (**Time Complexity is o(n) and o(h) space where h is max height**)

LINK FOR THE INORDER TRAVERSAL STACK METHOD

Point : [first we go till down left then we print the value then we make curr to to it's right if it's right is NULL like in case of 4 then again pop the stack and do with 2 now it's curr->right is not NULL now do same approach of go to left ]

Pre-order(**Time Complexity is o(n) and o(h) space where h is max height**)

In this everything is same as In-order it is just here we would print the root when we are going to add it and traverse to it's left and rest is same

CODE

code

Least Common Ancestor

Binary Search Tree

IT will help you for LCA in BST

Now if both nodes are one side then go to that side , but when the both nodes are apart then break at that node(U) which separate them and that node(U) will be the answer as after that node(U) , no node will contain both the required nodes.

Now if the LCA is one of the the required node like in this case, so in this it means there is no node (U) which cover both nodes, so the node(one of the required nodes) with greater height than other will be answer , like here 8 for 8 and 14

 U can see for 8 and 14 , here 8 is the answer

Its for LCA in Binary Tree

In this Backtracking was involved.

Extra I really liked this question , you can try this !

Number of Binary Search Trees from the Given length of Preorder sequence

Proof

one more point

ok

Thank you so much guys! for reading this blog!!!

Full text and comments »

  • Vote: I like it
  • +18
  • Vote: I do not like it