#preorder traversal

[sufiblackmamba]

[kuriyeedu]

Leetcode Q#114

Flatten binary tree to linked list

Solution Strategy:

Preorder traversal of the tree gives the ordering Root->Left->Right

Use this traversal to do the following:

temp = root->right; root->right = root->left; root->right->right = temp; // more appropriately, lastNode of left tree’s flattened linked list->right = temp; root->left = NULL;

Apply this solution recursively on tree’s left and right subtrees.

Complexity O(n^2) - As after flattening out every left tree, you will have to traverse the linked list to the find the last element to which the root->right needs to be attached.

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void flatten(TreeNode* root) { if (!root) { return; } if (root->left){ flatten(root->left); } if (root->right){ flatten(root->right); } if (root->left){ TreeNode* p = root->left; while(p->right){ p = p->right; } TreeNode* temp = root->right; root->right = root->left; p->right = temp; root->left = NULL; } return ; } };

[ictjobs-blog]

New Post has been published on Learning Hub

New Post has been published on http://ictjobs.info/program-construct-balanced-binary-tree-sorted-array/

C Program to Construct a Balanced Binary Tree using Sorted Array

#include <stdio.h> #include <stdlib.h> struct btnode int value; struct btnode *l; struct btnode *r; ; typedef struct btnode N; N* bst(int arr[], int first, int last); N* new(int val); void display(N *temp); int main() int arr[] = 10, 20, 30, 40, 60, 80, 90; N *root = (N*)malloc(sizeof(N)); int n = sizeof(arr) / sizeof(arr[0]), i; printf("Given sorted array is\n"); for (i = 0;i < n;i++) printf("%d\t", arr[i]); root = bst(arr, 0, n - 1); printf("\n The preorder traversal of binary search tree is as follows\n"); display(root); printf("\n"); return 0; /* To create a new node */ N* new(int val) N* node = (N*)malloc(sizeof(N)); node->value = val; node->l = NULL; node->r = NULL; return node; /* To create a balanced binary search tree */ N* bst(int arr[], int first, int last) int mid; N* temp = (N*)malloc(sizeof(N)); if (first > last) return NULL; mid = (first + last) / 2; temp = new(arr[mid]); temp->l = bst(arr, first, mid - 1); temp->r = bst(arr, mid + 1, last); return temp; /* To display the preorder */ void display(N *temp) printf("%d->", temp->value); if (temp->l != NULL) display(temp->l); if (temp->r != NULL) display(temp->r);

Output

Given sorted array is 10 20 30 40 60 80 90 The preorder traversal of binary search tree is as follows 40 - > 20 - > 10 - > 30 - > 80 - > 60 - > 90

[ictjobs-blog]

New Post has been published on Learning Hub

New Post has been published on http://ictjobs.info/program-find-smallest-largest-elements-binary-search-tree/

C Program To Find the Smallest and Largest Elements in the Binary Search Tree

#include <stdio.h> #include <stdlib.h> struct btnode int value; struct btnode *l; struct btnode *r; *root = NULL; typedef struct btnode N; N* new(int); void create(); void preorder(N *t); void min_max(N *t); void main() int choice; create(); while (1) printf("Enter the choice\n"); printf("1-Display : 2-Min & Max element : 3-Exit\n"); scanf("%d", &choice); switch (choice) case 1: printf("preorder preorder of tree elements\n"); preorder(root); printf("\n"); break; case 2: min_max(root); break; case 3: exit(0); default: printf("Enter the right choice\n"); /* creating temporary node */ N* new(int data) N* temp = (N*)malloc(sizeof(N)); temp->value = data; temp->l = NULL; temp->r = NULL; return(temp); /* Creating the binary search tree */ void create() root = new(40); root->l = new(20); root->r = new(60); root->l->l = new(10); root->l->r = new(30); root->r->r = new(80); root->r->r->r = new(90); /* To display preorder traversal of the tree */ void preorder(N *temp) printf("%d->", temp->value); if (temp->l != NULL) preorder(temp->l); if (temp->r != NULL) preorder(temp->r); /* TO find the minimum and maximum values in the given tree */ void min_max(N *temp) while (temp->l != NULL) temp = temp->l; printf("Minimum value = %d\n", temp->value); temp = root; while (temp->r != NULL) temp = temp->r; printf("Maximum value = %d\n", temp->value);

Output

Enter the choice 1 -Display : 2 -Min & Max element : 3 -Exit 1 preorder preorder of tree elements 40 - > 20 - > 10 - > 30 - > 60 - > 80 - > 90 Enter the choice 1 -Display : 2 -Min & Max element : 3 -Exit 2 Minimum value = 10 Maximum value = 90 Enter the choice 1 -Display : 2 -Min & Max element : 3 -Exit 3

[expectzero-blog]

Pseudocode for Constructing a binary tree from its preorder and inorder traversal.

Lets say there is a tree as follows.                       1                 /             \             2                 3         /       \           /      \      4          5        6       7

Inorder Traversal :  4 2 5 1 6 3 7 Preorder Traversal : 1 2 4 5 3 6 7.

We will built a binary from the inorder and preorder traversal .

Lets call the function with the following parameters with the root containing the pointer to the newly created tree. root = builtTree(inorderArray,0,inorderArray.size-1,0)

Struct node { int data; node * left; node* right; }

node buildTree( int[] inorderArray, int start , int end, int pos) { if (inorderArray==null) return null; node elem = new mode(); if(start==end) { elem->data = inorderArray[pos]; return node; } else { pos = findElementInPreoder(inorderArray,start,end,pos); node->left = buildTree( inorderArray, 0, pos-1, pos++); node->right = buildTree( inorderArray, pos+1, end, pos++); } } }

int findElementInPreoder(int[] inorderArray, start,end,int pos) { for (int i = start;i<=end;i++) { if(inorderArray[i]==preorderArray[pos]) { return i; } } }