The post-order traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The…

To determine the height of the binary tree, we reconstruct the tree using the given post-order and in-order traversals.

Step 1: In post-order traversal, the last element is the root of the tree. Here, the post-order traversal is 8, 9, 6, 7, 4, 5, 2, 3, 1. Therefore, the root of the tree is 1.

Step 2: In in-order traversal, the elements to the left of the root belong to the left subtree, and the elements to the right belong to the right subtree. The in-order traversal is 8, 6, 9, 4, 7, 2, 5, 1, 3. So, the left subtree contains 8, 6, 9, 4, 7, 2, 5, and the right subtree contains 3.

Step 3: Recursively apply the same logic to the left subtree. The post-order traversal of the left subtree is 8, 9, 6, 7, 4, 5, 2. The last element, 2, is the root of the left subtree.

Step 4: In the in-order traversal of the left subtree, 8, 6, 9, 4, 7 are to the left of 2, and 5 is to the right. So, 5 is the right child of 2, and the left subtree of 2 contains 8, 6, 9, 4, 7.

Step 5: Continue this process to reconstruct the entire tree. The right subtree of the root (1) is a single node, 3, so it has no children.

Step 6: The height of the tree is the length of the longest path from the root to any leaf. The longest path goes through the left subtree, which has a depth of 3, and the root, making the total height 4.

Therefore, the height of the binary tree is 4.

हिन्दी उत्तर:

बाइनरी ट्री की ऊँचाई निर्धारित करने के लिए, हम दिए गए पोस्ट-ऑर्डर और इन-ऑर्डर ट्रैवर्सल का उपयोग करके ट्री का पुनर्निर्माण करते हैं।

चरण 1: पोस्ट-ऑर्डर ट्रैवर्सल में अंतिम तत्व ट्री का जड़ होता है। यहाँ, पोस्ट-ऑर्डर ट्रैवर्सल 8, 9, 6, 7, 4, 5, 2, 3, 1 है। इसलिए, ट्री का जड़ 1 है।

चरण 2: इन-ऑर्डर ट्रैवर्सल में, जड़ के बाईं ओर के तत्व बाईं उप-ट्री के होते हैं, और दाईं ओर के तत्व दाईं उप-ट्री के होते हैं। इन-ऑर्डर ट्रैवर्सल 8, 6, 9, 4, 7, 2, 5, 1, 3 है। इसलिए, बाईं उप-ट्री में 8, 6, 9, 4, 7, 2, 5 हैं, और दाईं उप-ट्री में 3 है।

चरण 3: बाईं उप-ट्री पर इसी तरह की तर्क लागू करें। बाईं उप-ट्री का पोस्ट-ऑर्डर ट्रैवर्सल 8, 9, 6, 7, 4, 5, 2 है। अंतिम तत्व, 2, बाईं उप-ट्री का जड़ है।

चरण 4: बाईं उप-ट्री के इन-ऑर्डर ट्रैवर्सल में, 8, 6, 9, 4, 7 2 के बाईं ओर हैं, और 5 दाईं ओर है। इसलिए, 5, 2 का दाईं बच्चा है, और 2 की बाईं उप-ट्री में 8, 6, 9, 4, 7 हैं।

चरण 5: इस प्रक्रिया को जारी रखें ताकि पूरी ट्री का पुनर्निर्माण किया जा सके। जड़ (1) की दाईं उप-ट्री एक एकल नोड, 3, है, इसलिए इसके कोई बच्चे नहीं हैं।

चरण 6: ट्री की ऊँचाई जड़ से किसी भी पत्ते तक की सबसे लंबी पथ की लंबाई है। सबसे लंबा पथ बाईं उप-ट्री से गुजरता है, जिसकी गहराई 3 है, और जड़, जिससे कुल ऊँचाई 4 होती है।

इसलिए, बाइनरी ट्री की ऊँचाई 4 है।