Tree in data structure

Tree
• A tree is an abstract model of a hierarchical structure that consists of
nodes with a parent-child relationship.
• Tree is a sequence of nodes
• There is a starting node known as a root node
• Every node other than the root has a parent node.
• Nodes may have any number of children

Some Key Terms:
• Root− Node at the top of the tree is called root.
• Parent− Any node except root node has one edge upward to a node called parent.
• Child− Node below a given node connected by its edge downward is called its child node.
• Sibling – Child of same node are called siblings
• Leaf − Node which does not have any child node is called leaf node.
• Sub tree − Sub tree represents descendants of a node.
• Levels − Level of a node represents the generation of a node. If root node is at level 0, then its next child node is at level 1, its grandchild is at level 2 and so on.
• keys − Key represents a value of a node based on which a search operation is to be carried out for a node.

Some Key Terms:

 Degree of a node: -> The degree of a node is the number of children of that node
• Degree of a Tree:  ->The degree of a tree is the maximum degree of nodes in a given tree
 • Path:  ->It is the sequence of consecutive edges from source node to destination node.
 • Height of a node: -> The height of a node is the max path length form that node to a leaf node.
• Height of a tree: ->  The height of a tree is the height of the root
• Depth of a tree :  -> Depth of a tree is the max level of any leaf in the tree

Binary Search Tree(BST)

• A binary search tree (BST) is a binary tree that is either empty or in which every node contains a key (value) and satisfies the following conditions: • All keys in the left sub-tree of the root are smaller than the key in the root node • All keys in the right sub-tree of the root are greater than the key in the root node • The left and right sub-trees of the root are again binary search trees

Binary Search Tree(BST)
• A binary search tree is basically a binary tree, and therefore it can be traversed in inorder, preorder and postorder.
• If we traverse a binary search tree in inorder and print the identifiers contained in the nodes of the tree, we get a sorted list of identifiers in ascending order.

Why Binary Search Tree?

• Let us consider a problem of searching a list.

• If a list is ordered searching becomes faster if we use contiguous list(array).

• But if we need to make changes in the list, such as inserting new entries or deleting old entries, (SLOWER!!!!) because insertion and deletion in a contiguous list requires moving many of the entries every time.

• So we may think of using a linked list because it permits insertion and deletion to be carried out by adjusting only few pointers.
• But in an n-linked list, there is no way to move through the list other than one node at a time, permitting only sequential access.
• Binary trees provide an excellent solution to this problem. By making the entries of an ordered list into the nodes of a binary search tree, we find that we can search for a key in O(logn)

For more informatio:->
https://l.facebook.com/l.php?u=https%3A%2F%2Fdrive.google.com%2Ffile%2Fd%2F1T971D3owoG-jeigPlLH1u9ocxkPhYnWc%2Fview%3Fusp%3Dsharing%26fbclid%3DIwAR0PoXgycOIxJM5_nPwB4UxEO_OyKVj792WLwjSTFplT0BAPzeSOnSsJbJ0&h=AT0r16o9XEpDYdUZHNEaDk0CKPOofxEUvDlxUdMVPV-Sz7NTahiY6LfZqM9BRq5_7zvVokO_697ecsl75g4A-x_bAAdnZMWDhLVuPnIobUv7O5Pe-E-Spz22NDp1VEZRPo0FFg