Binary Tree

आकार और शब्द

        1
       / \
      2   3
     / \
    4   5

शीर्ष पर root, नीचे leaves। Height सबसे लंबा root-से-leaf पथ है। संतुलित tree की height ~log n; बिगड़ी हुई एक linked list है जिसकी height n।

चार traversal

Depth-first: pre/in/post-order केवल इसमें भिन्न कि node को कब देखते हैं बनाम recurse। Breadth-first queue उपयोग करता है, स्तर दर स्तर।

def inorder(node, out):
    if not node: return
    inorder(node.left, out)
    out.append(node.val)     # visit between children
    inorder(node.right, out)

from collections import deque
def bfs(root):
    q, out = deque([root]), []
    while q:
        n = q.popleft()
        out.append(n.val)
        if n.left:  q.append(n.left)
        if n.right: q.append(n.right)
    return out

संगठन चार्ट

CEO root है; हर प्रबंधक के नीचे रिपोर्ट। सबको बताने के लिए विभाग-गहराई (DFS) या मंज़िल-दर-मंज़िल (BFS) जा सकते हैं।

इंटरव्यू पैटर्न

अधिकांश tree समस्याएँ एक recursive फ़ंक्शन हैं जो children से जानकारी लौटाता है (height, sum, is-balanced, LCA)। सोचें: "इस node के लिए उत्तर देने को मुझे left और right से क्या चाहिए?"