What is Binary Search Tree?

  • Introduction

  • Root Node

  • Edge

  • Parent

  • Child

  • Leaf Node

  • Internal Node

  • Level

  • Height

  • Sub Tree

Introduction

A Binary search tree (BST) is type of tree.They are contains left subtree and right subtree. leaf subtree element contain less then root of BST and right subtree element contain value are grater then and equal to root.

Example

531486595475510572656447548583450 Binary search tree Edit Tree

Root Node

First inserted element of BST is root of tree. Root node is starting point of Binary search tree.

Example

424410448561475494402540409447

424 is root of BST. Root is top element of tree.

Edge

Connected BST nodes it is called Edge. Number of Node-1 Edge are possible in Binary search tree.

Example

Edit Tree Click Here

527485541591551511579496495403 Binary search tree

In this Tree Number of Node is 10 and connected Edge is 9 (N-1).

Parent node

The node which has child it is call Parent node .

Example

Edit Tree Click Here

450528420588449530515496457447200

Parent node is 420 449 450 496 515 528 588.

Child Node

The node which is descendant of any node is called as CHILD Node of BST. Binary search tree only at most two child node of parent node.

Example

Edit Tree Click Here

543524497595470472534452474448

524 and 595 is child of 543

497 and 534 is child of 524

470 is child of 497

452 and 472 is child of 470

448 is child of 452

474 is child of 472

Leaf Node

No left and right child of any node it is called Leaf Node of Tree. In Other Word no left and right subtree it is called left node.

Example

Edit Tree Click Here

548500571545435440452508563514800

leaf node : 452 514 563 800

Interal Node

At least one child (Left child or right child) of node that is called Internal Node of BST. Internal node also know as none leaf node .

Example

Edit Tree Click Here

519536460413517569507410570480

None leaf node (internal node) is : 413 460 507 517 519 536 569

Level

Level of BST Top to bottom nodes. Root node of BST at level 0. And other bottom level increment by one.

Example

Edit Tree Click Here

Level 0Level 1Level 2Level 3Level 4 520412409567556555429512580538

Height

Longest distance between leaf node to any particular node that is called height of this particular node. And height of BST tree is Root node to longest leaf node.

Example

Edit Tree Click Here

480541524412471506569564487586

Note: Height is Counting by nodes or edges.

Height of tree by node is : 5

Height of tree by edges is : 4