Tree — Part 1
Hello, in this story series I want to talk about Tree Data Structure, but according to Tree complexity I break the story in different parts and this story is the first part, that I am going to talk about initial elements.
We have different details of tree’s which names are :
1- Tree
2- Binary Tree
3- Binary Search Tree
4- Balanced and Unbalanced
4.1- Complete Binary Trees
4.2- Full Binary Trees
4.3- Perfect Binary Trees
And also we have different approaches for searching, Deleting, Adding, and Updating value in Tree data structure that talks about a small of them in this story continue.
before talking about CRUD in tree data structure let me see a part of Cracking the coding interview Book that explain a part of different between Tree structure.
Trees vs. Binary Trees
A binary tree is a tree in which each node has up to two children. Not all trees are binary trees. For example, this tree is not a binary tree. You could call it a ternary tree.
Binary Tree vs. Binary Search Tree
A BST(Binary Search Tree) is a binary tree in symmetric order*.
(A binary tree is either empty or two disjoint binary tree (left and right)).
*Symmetric Order is each node has a key and every nodes key is :
1- larger than all keys in it’s left sub-tree
2- smaller than all keys in it’s right sub-tree
Balanced vs. Unbalanced
a. Complete Binary Trees is a binary tree in which every level of the tree is fully filled, except for perhaps the last level. To the extent that the last level is filled, it is filled left to right.
b.Full Binary Trees is a full binary tree is a binary tree in which every node has either zero or two children. That is, no nodes have only one child.
c.Perfect Binary Trees is one that is both full and complete. All leaf nodes will be at the same level, and this level has the maximum number of nodes.
let me have a brief look at part of my favorable searching, deleting, moving, inserting, and other approaches.
the first point we should know, is What is Simple Node?
Why we call it simple node ?!!! because we will talk about Node with different fields that help us to have better approach for complexity time and space in near future.
a Simple Node is a model that comprised of three fields:
. A value
. A reference to the left and right sub-tree.
and about searching on the tree I should write a below code that a simple way of searching but in future posts, we talk about different models of node and searching.
in the above code, you see we check three conditions and according to our conditions, we are traversing on the tree with recursion approach and finally if we could find value, return that, otherwise we return null.
before talking about how we can remove, insert, and other operations on the tree we need to talk about traversing way on the tree, so please follow the next story.
To access to the completed source, please check Room Project on this link, also you can find different challenges approach of LeetCode and HackerRank in the mentioned Link.
