{"id":76155,"date":"2024-07-19T11:00:58","date_gmt":"2024-07-19T15:00:58","guid":{"rendered":"https:\/\/bangla.sitestree.com\/?p=76155"},"modified":"2024-07-28T17:02:54","modified_gmt":"2024-07-28T21:02:54","slug":"input-tree-traversal-data-output-build-the-tree","status":"publish","type":"post","link":"http:\/\/bangla.sitestree.com\/?p=76155","title":{"rendered":"Input: Tree Traversal Data Output: Build the Tree"},"content":{"rendered":"\n
<\/figure>
\n

Problem: <\/p>\n\n\n\n

\"\"<\/a><\/figure>\n\n\n\n

<\/p>\n\n\n\n

Ref: Book on Data Structure and Algorithm in C<\/p>\n<\/div><\/div>\n\n\n\n

<\/figure>
\n

<\/p>\n\n\n\n

\"\"<\/a><\/figure>\n\n\n\n

<\/p>\n<\/div><\/div>\n\n\n\n

\u2022From In-order Output to Build the Tree<\/p>\n\n\n\n

\u2022Take In-order Traversal Output Data<\/p>\n\n\n\n

\u2022And Build the Tree<\/p>\n\n\n\n

\u2022Take the middle (N) or so as the root<\/p>\n\n\n\n

\u2022Keep going\/taking alternate left (nodeLabels) (K D) from there<\/p>\n\n\n\n

\u2022Make those also roots\/parents (left sub tree)<\/p>\n\n\n\n

\u2022The last may be at the last left in this flow<\/p>\n\n\n\n

\u2022Then from the last (left last of data)<\/p>\n\n\n\n

\u2022Take alternate nodeLabels (P, E) and make them the right child (in left side tree)<\/p>\n\n\n\n

\u2022From middle Keep going\/taking alternate right node labels (A L)<\/p>\n\n\n\n

\u2022Make center\/parent\/root (right subtree)<\/p>\n\n\n\n

\u2022From the end reverse back with the alternate nodes (T F)<\/p>\n\n\n\n

\u2022Make these as left children<\/p>\n\n\n\n

<\/p>\n\n\n\n

<\/p>\n\n\n\n

<\/figure>
\n

<\/p>\n\n\n\n

\"\"<\/a><\/figure>\n\n\n\n

<\/p>\n<\/div><\/div>\n\n\n\n

From Pre-order Tree Traversal Output to Build the Tree
First one becomes the root such as N
Some immediate ones (D G) also becomes parents up until middle (you can choose) \u2013 left sub tree parens

Then put some immediate ones (K P) as right children (in left subtree) to come to root

Then take alternate (E F L) to have the parents on the right (Goes Right, right subtree)

come back from right, take remaining (A, T), make them left children (bottom to up direction)<\/p>\n\n\n\n

<\/p>\n\n\n\n

<\/p>\n\n\n\n

<\/figure>
\n

<\/p>\n\n\n\n

\"\"<\/a><\/figure>\n\n\n\n

<\/p>\n<\/div><\/div>\n\n\n\n

\u2022Input: Post order Tree Traversal data, Output: Tree<\/p>\n\n\n\n

\u2022Last one (E) becomes the root<\/p>\n\n\n\n

\u2022Some immediate (backward) right ones ones (L A T) up until middle (you can choose)  also becomes parents (downward right side parent)<\/p>\n\n\n\n

\u2022\u2013 Then put some immediate ones (backward) ( N F ) as left  children to come to root

Then take alternate (K P) to have the parents on the left side of the tree<\/p>\n\n\n\n

\u2022Come back from the last, with the remaining ones (G D)<\/p>\n\n\n\n

\u2022and make right children (left sub tree)<\/p>\n","protected":false},"excerpt":{"rendered":"

\u2022From In-order Output to Build the Tree \u2022Take In-order Traversal Output Data \u2022And Build the Tree \u2022Take the middle (N) or so as the root \u2022Keep going\/taking alternate left (nodeLabels) (K D) from there \u2022Make those also roots\/parents (left sub tree) \u2022The last may be at the last left in this flow \u2022Then from the … <\/p>\n

Continue reading<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[1966,1883,182],"tags":[],"class_list":["post-76155","post","type-post","status-publish","format-standard","hentry","category-data-structure-and-algorithms","category---data-structure","category---blog","item-wrap"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[{"id":76183,"url":"http:\/\/bangla.sitestree.com\/?p=76183","url_meta":{"origin":76155,"position":0},"title":"Struct and Tree Node Examples","author":"Sayed","date":"July 20, 2024","format":false,"excerpt":"#include #include #pragma warning(disable : 4996) #define MaxWordSize 100 \/\/ Declare a structure that holds data in a node typedef struct { int num; } NodeDataInt; \/\/ Declare a structure that holds data in a node typedef struct { char word[MaxWordSize + 1]; int freq; } NodeDataChar; \/\/\u2026","rel":"","context":"In "Data Structure and Algorithms"","block_context":{"text":"Data Structure and Algorithms","link":"http:\/\/bangla.sitestree.com\/?cat=1966"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":76185,"url":"http:\/\/bangla.sitestree.com\/?p=76185","url_meta":{"origin":76155,"position":1},"title":"A Binary Tree Declaration","author":"Sayed","date":"July 20, 2024","format":false,"excerpt":"#include #include \/\/ Declare a structure that holds data in a node typedef struct { int num; } NodeData; typedef struct treeNode { NodeData data; struct treeNode* left, * right; } TreeNode, *TreeNodePtr; typedef struct { TreeNodePtr root; } BinaryTree; \/\/ main method int main() { \/\/ NULL\u2026","rel":"","context":"In "Data Structure and Algorithms"","block_context":{"text":"Data Structure and Algorithms","link":"http:\/\/bangla.sitestree.com\/?cat=1966"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":76181,"url":"http:\/\/bangla.sitestree.com\/?p=76181","url_meta":{"origin":76155,"position":2},"title":"Struct and Tree Node","author":"Sayed","date":"July 20, 2024","format":false,"excerpt":"\/\/ Ref: typedef and struct \/\/ https:\/\/www.w3resource.com\/c-programming-exercises\/c-snippets\/difference-between-typedef-struct-and-struct-definitions-with-example.php#google_vignette \/\/ https:\/\/www.tutorialspoint.com\/cprogramming\/c_pointers.htm \/\/ https:\/\/www.geeksforgeeks.org\/typedef-in-c\/ #pragma warning(disable : 4996) #include #include \/\/ Declare a structure that holds data in a node typedef struct { int num; } NodeData; \/\/ define what a node will look like typedef struct treenode { NodeData data;\u2026","rel":"","context":"In "Data Structure and Algorithms"","block_context":{"text":"Data Structure and Algorithms","link":"http:\/\/bangla.sitestree.com\/?cat=1966"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":76152,"url":"http:\/\/bangla.sitestree.com\/?p=76152","url_meta":{"origin":76155,"position":3},"title":"Input: Post order Tree Traversal data, Output: Tree","author":"Sayed","date":"July 19, 2024","format":false,"excerpt":"\u2022 Last one (E) becomes the root \u2022 Some immediate (backward) right ones ones (L A T) up until middle (you can choose)\u00a0 also becomes parents (downward right side parent) \u2022 \u2013 Then put some immediate ones (backward) ( N F ) as left\u00a0 children to come to rootThen take\u2026","rel":"","context":"In "Data Structure and Algorithms"","block_context":{"text":"Data Structure and Algorithms","link":"http:\/\/bangla.sitestree.com\/?cat=1966"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/bangla.sitestree.com\/wp-content\/uploads\/2024\/07\/image-3.png?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/bangla.sitestree.com\/wp-content\/uploads\/2024\/07\/image-3.png?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/bangla.sitestree.com\/wp-content\/uploads\/2024\/07\/image-3.png?resize=525%2C300&ssl=1 1.5x, https:\/\/i0.wp.com\/bangla.sitestree.com\/wp-content\/uploads\/2024\/07\/image-3.png?resize=700%2C400&ssl=1 2x"},"classes":[]},{"id":76187,"url":"http:\/\/bangla.sitestree.com\/?p=76187","url_meta":{"origin":76155,"position":4},"title":"C Code Build a Binary Tree.","author":"Sayed","date":"July 20, 2024","format":false,"excerpt":"#include #include #include #pragma warning(disable : 4996) #define MaxWordSize 100 \/\/ Declare a structure that holds data in a node typedef struct { char word[MaxWordSize + 1]; } NodeData; typedef struct treeNode { NodeData data; struct treeNode* left, * right; } TreeNode, *TreeNodePtr; typedef struct { TreeNodePtr\u2026","rel":"","context":"In "Data Structure and Algorithms"","block_context":{"text":"Data Structure and Algorithms","link":"http:\/\/bangla.sitestree.com\/?cat=1966"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":76201,"url":"http:\/\/bangla.sitestree.com\/?p=76201","url_meta":{"origin":76155,"position":5},"title":"Steps to Create a Binary Search Tree","author":"Sayed","date":"July 28, 2024","format":false,"excerpt":"If binary tree is empty, create a node, and assign data, point to itOtherwise : point to root node Compare the new - data - to - insert with the current node dataWe maintain a pointer say current to point to the node under visit If data matched : nothing\u2026","rel":"","context":"In "Data Structure and Algorithms"","block_context":{"text":"Data Structure and Algorithms","link":"http:\/\/bangla.sitestree.com\/?cat=1966"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=\/wp\/v2\/posts\/76155","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=76155"}],"version-history":[{"count":1,"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=\/wp\/v2\/posts\/76155\/revisions"}],"predecessor-version":[{"id":76160,"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=\/wp\/v2\/posts\/76155\/revisions\/76160"}],"wp:attachment":[{"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=76155"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=76155"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=76155"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}