---
# System prepended metadata

title: Binary Tree implementaiton
tags: [tree, data structure]

---

# Binary Tree implementaiton


logic View


![](https://hackmd.io/_uploads/BkH3klEKn.png)


## Empty Tree 

```cpp
struct  bstNode
{
    int data;
    struct bstNode* left ;
    struct bstNode* right;
};


int main(){

    //to store addres of root node 
    struct bostNode* rootPtr;
    rootPtr = NULL;

}
```

## Insert Function 

insert(root address, value)

Insert First Node
![](https://hackmd.io/_uploads/ry4vvYSt3.png)

```

struct bstNode* insertF(struct bstNode* rootPtr, int value){
    if (rootPtr == NULL){
        rootPtr = createNewNode(value);
        return rootPtr;
    }
}

```

Left sub node and Right sub node 

![](https://hackmd.io/_uploads/SJVKtKBt2.png)

```
struct bstNode* insertF(struct bstNode* rootPtr, int data){
    if (rootPtr == NULL){
        rootPtr = createNewNode(data);
        return rootPtr;
    }
    else if (data <= rootPtr->data){
        rootPtr->left = insertF(rootPtr->left,data); //rootPtr(200)->left = NULL  create Node 
    }
    else {
        rootPtr->right = insertF(rootPtr->right,data);
    }
    return rootPtr;
}
```
if insert(rootptr,5)

main()
insert(200,5) return 200 
insert(150,5) return 150 
insert(0,5) return 100 (New Node Address) 


### Create a New Node Function 

建立一個新Node

```cpp
struct bstNode* createNewNode(int value){
    struct bstNode* newNodePtr = new bstNode();//return create new node arddess from the Heap
    newNodePtr->data=value;
    newNodePtr->left = newNodePtr->right = NULL;
    return newNodePtr;
}
```


### pointer to pointer 寫法


可以不用return pointer address 
```cpp

// pointer to pointer -> void 

// void insertF(struct bstNode** rootPtr, int value){
//     if (*rootPtr == NULL){
//         *rootPtr = createNewNode(value);
//     }
// };

// int main(){

//     //to store addres of root node 
//     struct bstNode* rootPtr = NULL;
//     insertF(&rootPtr,1);
//     insertF(&rootPtr,2);
//     insertF(&rootPtr,3);

   
// }

```

## Search function IN BST


```
bool searchF(struct bstNode* rootPtr, int SearchValue){
    if (rootPtr == NULL) return false;
    else if (rootPtr->data == SearchValue) return true;

    //walk to child
    else if (SearchValue <= rootPtr->data) return searchF(rootPtr->left,SearchValue);
    else return searchF(rootPtr->right,SearchValue); 
}
```


## Code and result 


```cpp!
#include<iostream>
using namespace std;

struct  bstNode
{
    int data;
    struct bstNode* left ;
    struct bstNode* right;
};


struct bstNode* createNewNode(int data){
    struct bstNode* newNodePtr = new bstNode();//return create new node arddess from the Heap
    newNodePtr->data=data;
    newNodePtr->left = newNodePtr->right = NULL;
    return newNodePtr;
}

struct bstNode* insertF(struct bstNode* rootPtr, int data){
    if (rootPtr == NULL){
        rootPtr = createNewNode(data);
        return rootPtr;
    }
    else if (data <= rootPtr->data){
        rootPtr->left = insertF(rootPtr->left,data); //rootPtr(200)->left = NULL  create Node 
    }
    else {
        rootPtr->right = insertF(rootPtr->right,data);
    }
    return rootPtr;
}


// pointer to pointer -> void 

// void insertF(struct bstNode** rootPtr, int data){
//     if (*rootPtr == NULL){
//         *rootPtr = createNewNode(data);
//     }
// };

// int main(){

//     //to store addres of root node 
//     struct bstNode* rootPtr = NULL;
//     insertF(&rootPtr,1);
//     insertF(&rootPtr,2);
//     insertF(&rootPtr,3);

   
// }

bool searchF(struct bstNode* rootPtr, int SearchValue){
    if (rootPtr == NULL) return false;
    else if (rootPtr->data == SearchValue) return true;

    //walk to child
    else if (SearchValue <= rootPtr->data) return searchF(rootPtr->left,SearchValue);
    else return searchF(rootPtr->right,SearchValue); 
}

int main(){

    //to store addres of root node 
    struct bstNode* rootPtr;
    rootPtr = NULL;
    rootPtr = insertF(rootPtr,15);
    rootPtr = insertF(rootPtr,10);
    rootPtr = insertF(rootPtr,20);

    int number;
    printf("enterthe Number \n");
    scanf("%d",&number);
    if (searchF(rootPtr,number)== true) printf("found\n");
    else printf("not found");
   
}



```

Result 

```
PS C:\Users\USER\Desktop\NQUCS\DataStructure_C-CPP\tree> .\binaryTreeDynamicNode.exe
enterthe Number 
10
found
```