Binary Tree Problems Must for Interviews and Competitive Coding (Aditya Chatterjee Srishti Guleria Ue Kiao)（Z-Library）
, ,
Data Structures and Algorithms
This book "Binary Tree Problems" is carefully crafted to present you the knowledge and practice (around the data structure, Binary Tree) needed to ace Coding Interviews and Competitive Coding Contests. The book takes you through the fundamentals of Binary Tree, presents how to implement it in a good and secure way, make you practice key problems, present variants like Threaded Binary Tree, Binary Space Partitioning Tree, Skewed Binary Tree, AVL Tree, Treap and much more. The content covered is deep and is not covered by any other standard book. Each chapter is followed by a brief note of insight which wraps up your though in the correct direction and is a feast for budding Independent Researchers. If you aspire you to a good Software Developer, you should definitely get this book. You will be prepared to apply Binary Tree is designing solutions to key real life problems like designing an Excel sheet or making Game Graphics render fast. Authors: Aditya Chatterjee; Srishti Guleria; Ue Kiao. Contributors (16): Benjamin QoChuk, Hrithik Shrivastava, Parth Maniyar, Priyanshi Sharma, Rohit Topi, Amruta U. Koshe, Ayush Sonare, Akshay Gopani, Rashmitha, Manasvi Singh, Sahil Silare, Vaibhav Gupta, Vishnu S Reddy, Kyatham Srikanth, Rupali Kavale, Yash Aggarwal.
6
Views
Registered users can read the full content for free
Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.
Page
1
(This page has no text content)
Page
2
(This page has no text content)
Page
3
(This page has no text content)
Page
4
Binary Tree Problems Must for Interviews and Competitive Coding Aditya Chatterjee, Srishti Guleria, Ue Kiao iq.OPENGENUS.org
Page
5
About this book This book “Binary Tree Problems ” is carefully crafted to present you the knowledge and practice (around the data structure, Binary Tree ) needed to ace Coding Interviews and Competitive Coding Contests. The book takes you through the fundamentals of Binary Tree, presents how to implement it in a good and secure way, make you practice key problems, present variants like Threaded Binary Tree, Binary Space Partitioning Tree, Skewed Binary Tree, AVL Tree, Treap and much more. The content covered is deep and is not covered by any other standard book. Each chapter is followed by a brief note of insight which wraps up your though in the correct direction and is a feast for budding Independent Researchers . If you aspire you to a good Software Developer, you should definitely get this book. You will be prepared to apply Binary Tree is designing solutions to key real life problems like designing an Excel sheet or making Game Graphics render fast. If you face any doubt, you can reach us by email: team@opengenus.org Authors : Aditya Chatterjee; Srishti Guleria; Ue Kiao ; About the Authors: Aditya Chatterjee is an Independent Researcher and the Founding Member of OPENGENUS, a scientific community focused on Computing Technology. Srishti Guleria is a Maintainer and Software Developer, Intern at OpenGenus specializing in Tree Data Structures. She is a Computer Science student at Rajasthan Technical University, Kota. Ue Kiao is a Japanese Software Developer and has played key role in designing systems like TaoBao, AliPay and many more. She has completed her B. Sc in Mathematics and Computing Science at National Taiwan University and PhD at Tokyo Institute of Technology.
Page
6
Contributors (16) : Benjamin QoChuk, Hrithik Shrivastava, Parth Maniyar, Priyanshi Sharma, Rohit Topi, Amruta U. Koshe, Ayush Sonare, Akshay Gopani, Rashmitha, Manasvi Singh, Sahil Silare, Vaibhav Gupta, Vishnu S Reddy, Kyatham Srikanth, Rupali Kavale, Yash Aggarwal; All Contributors are associated with OpenGenus. Published: May 2021 © iq.OpenGenus.org Table of Contents # Chapter 1 Binary Tree 2 Properties of Binary Tree 3 Implementation of Binary Tree 4 Implementation of Binary Tree with no NULL 5 Intuitive View of a Binary Tree 6 Traversing a Binary Tree (Preorder, Postorder, Inorder) 7 Convert Inorder+Preorder to Binary Tree (+ other combinations) 8 Find height or depth of a Binary Tree 9 Find Level of each node from root node 1 0 Diameter of a Binary Tree 1 2 Check if a Binary Tree is Balanced by Height 1 3 Find number of Universal Value subtrees in a Binary Tree 1 4 Counting subtrees where nodes sum to a specific value
Page
7
1 5 Find if a given Binary Tree is a Sub-Tree of another Binary Tree 1 6 Check if a Binary Tree has duplicate values 1 7 Find nodes which are at a distance k from root in a Binary Tree 1 8 Finding nodes at distance K from a given node 1 9 Find ancestors of a given node in a binary tree 2 0 Largest Independent Set in Binary Tree 2 1 Copy a binary tree where each node has a random pointer 2 2 Serialization and Deserialization of Binary Tree 2 3 0-1 Encoding of Binary Tree 2 4 ZigZag Traversal of Binary Tree 2 5 Check if 2 Binary Trees are isomorphic 2 6 Convert Binary Tree to Circular Doubly Linked list 2 7 Introduction to Skewed Binary Tree 2 8 Check if Binary Tree is skewed or not 2 9 Change Binary Tree to Skewed Binary Tree
Page
8
3 0 Threaded Binary Tree 3 1 Operations in Threaded Binary Tree 3 2 Convert Binary Tree to Threaded Binary Tree 3 3 Binary Search Tree 3 4 Converting a Sorted Array to Binary Tree 3 5 Minimum number of swaps to convert a binary tree to binary search tree 3 6 Find minimum or maximum element in Binary Search Tree 3 7 Convert Binary Search Tree to Balanced Binary Search Tree 3 8 Find k-th smallest element in Binary Search Tree 3 9 Sum of k smallest elements in Binary Search Tree 4 0 Different Self Balancing Binary Trees 4 1 AVL Tree 4 2 Splay Tree 4 3 Binary Space Partitioning Tree 4 4 Binary Heap
Page
9
4 5 Treap 4 6 Some real problems 4 7 Applications & Concluding Note Binary Tree A binary tree is a data structure in which each element links to at most two other elements. It is represented by a starting element from which we can reach the other elements by following the links. Each element is known as a Node and the starting node of a Binary Tree is known as Root. In a Binary Tree, every node has at most 2 children that is the left child (left sub-tree) and the right child (right sub-tree). Node of a binary tree will look as follows: You can see that a node consists of three components: Pointer to left child node Data Pointer to right child node To put this in perspective, think of Linked List data structure where each element links to at most one element. Hence, this is a multi-dimensional version of Linked List.
Page
10
You can extend this idea to a generalized structure where each node points to at most N other nodes. This structure is known as N-ary Tree. Hence, Binary Tree is an 2-ary Tree. Suppose there is a binary tree of height "H". The height of root is considered to be 0 as a convention. Consider this diagram to understand the idea of height of each node: There are four types of binary trees: Complete Binary Tree Perfect Binary Tree Full Binary Tree Balanced Binary Tree Complete Binary Tree : A Binary Tree is complete Binary Tree if all levels are completely filled except the last level and last level should have all nodes as left as possible. Perfect Binary Tree : A Perfect Binary Tree is a binary tree in which all interior nodes have two children, and all leaves have the same depth that is same level. Full Binary Tree : A Full Binary Tree is a tree in which every node other than the leaves has two children.
Page
11
Balanced Binary Tree : A Balanced Binary Tree is a binary tree in which height of the tree is O(log N) where N is the number of nodes. Basic Operations A Binary Tree supports the following basic operations: Insertion: To insert new element into the Binary Tree Deletion: To delete a specific element from a Binary Tree Search/ Traversal: To go through all elements in a Binary Tree Insertion operation Suppose a binary tree is given with few allocated values. As given tree is binary tree, we can insert element wherever we want. Only one property of binary tree should be maintained, and property is that every node can have maximum two children. We need to insert the new element wherever we find the node whose left or right child is null. Given (Original Tree) : Inserting new element (5) in given tree Output (New Tree) :
Page
12
Deletion operation For deletion, first we need to find the element which we want to delete. The basic idea of deletion in a Binary Tree is to replace that element with the right most node (or copy) and then delete the rightmost node. Given (Original Tree) : Delete data 3. Deletion steps :
Page
13
By this way, deletion is done in binary trees. Time and Space Complexity Searching : For searching we need to traverse all elements so worst-case time complexity will be O(N) with a space complexity of O(1). Insertion : Worst case time complexity will be O(N) as it depends on the tree structure. You will understand this well as we move on). The space complexity is O(1). Deletion : Worst case time complexity will be O(N). The key idea is same as that of Insertion operation which we will understand better in later sections. The space complexity is O(1). Properties of a Binary Tree
Page
14
Let us consider that our Binary Tree has N elements. For simplicity, let us assume N is a power of 2. N = 2M Visualize the structure of a Balanced Binary Tree. The first level (0) will have 1 node (known as Root). The second level (1) will have 2 nodes. The third level will have 4 nodes which will be children of nodes at second level. Hence, at level (i), there will be 2(i) nodes. Assume we number the nodes starting from 1 to N in order (top to bottom and left to right). A sample graph will look like this: If we assume that such a numbering is done on a Complete Binary Tree (where every node has two child nodes expect the nodes at the last level), then the following points hold: Nodes are numbered as 1 to N Nodes in level “0” are [1] Nodes at level “i” are 2i to 2i+1 - 1 Nodes at the last level “H” are 2H to N Children of node “J” will be numbered as “2 x J” and “2 x J + 1” Parent of node “J” will be numbered “Floor(J/2)” These are key points which has two basic applications:
Page
15
Represent a Binary Tree as an array where the numbering is used as an index Use the numbering to find relationship between nodes. This can solve several challenging problems instantly. For a Binary Tree, we know the following about the height: Height can be N in the worst case where each node has at most 1 child node. The minimum height will be “log N”. This is the case of a perfectly balanced Binary Tree. The ideal case is to maintain the height to be close to “log N”. Having a height of N, decomposes a Binary Tree to an Array and there are no differences. A random Binary Tree achieves the height of “log N” on average. There are conditions or modifications of Binary Tree where the height is maintained to be “log N” at all times. The height directly impacts the performance of operations like Insert and Delete so it is preferred to keep it as low as possible. For a Binary Tree of height H, the maximum number of nodes will be 2 H+1 + 1 and the minimum number of nodes will be H . You can estimate the significant difference between the two cases. One is linear and the other is exponential. For a Complete Binary Tree of height H, the number of nodes will be from 2 H + 2 to 2 H+1 + 1 . Insight : With this, you have a strong idea of the bounds/ limitations of various aspects of a Binary Tree. This will help you in analyzing various algorithms and arrive at the time and space complexity easily.
Page
16
Implementation of Binary Tree We will implement a Binary Tree using OOP concepts. We will use a pseudocode which can be converted to the relevant Programming Language (like C++, Java, and Python) easily. A fundamental component is a Node which is defined as follows: class Node { int data ; // can be any datatype Node left ; // Left child node Node right ; // Right child node When we want to declare a group of data whether of similar or different data types, we use classes in Object Oriented Programming languages like C++ and Java. Other languages has the equivalent to group different datatypes together such as Structures (struct) in C. Our class is "Node" containing a pointer to left and pointer to right along with a data. Node left; is pointer to Left child node and stores the address of left child. Similarly, we have right child node. int data ; declares data of int (Integer) type. Nodes will be created in Heap memory as Dynamic Memory Allocation shall be used. This relates to malloc function in C and new function in C++ and returns a pointer to the object created. It is important to understand the concepts of stack and heap memory in dynamic allocation. For linked list, we keep the information of address of the head node. We can access all other nodes from head node using links. In this case, we know the address of the root node, which is must, without this we wot be able to access the tree using links.
Page
17
To declare the Binary tree, we will first need to create a pointer to Node that will store address of root node by : Node root . Our tree does not have any data yet, so let us assign our root node as NULL. Node root = NULL ; // Creating an empty tree As seen, we are assigning the left and right cells of nodes as addresses to their child and middle cell is for data. Identity of tree is the address of the root node, and we have declared a pointer to node in which we are storing address of root node. For empty tree, root pointer should be set as NULL. Consider this rootPtr (root pointer) as a different box pointing towards different nodes in our tree, and for pointing to different nodes we have to pass the address of the nodes. In the beginning, it is not pointing towards any node and therefore, it has NULL value. As we progressively add more nodes, we will change the address in this rootptr to point towards specific node in which we have to add the data. Node newNode = new Node() ; // Creates a new empty node "Node newNode=new Node(); " Returns the address of newly created node which we are collecting in variable newNode of type 'pointer to Node' because we can access heap memory using pointers. This variable now has structure of a doubly linked list in which data is assigned to data variable of 'newNode' and setting left and right child of 'newNode' as NULL then we are returning address of 'newNode' itself. If we have the data to be set along with the pointer/ link to Left child node and Right child node, then we can create a new empty node and set the attributes accordingly: Node newNode = new Node() ; // Creates a new empty node
Page
18
newNode -> Key = key ; newNode -> Left = Left_child ; newNode -> Right = Right_child ; Well, now our tree is empty, we have no data. Let us insert new data into our tree. For this we will call and define 'Insert' function. Firstly, we will have to call it in our main function as: Node insert(root node, data to be inserted); The key idea will be to: Create a new node with the data to be inserted Traverse the Binary Tree in order from left to right / top to bottom to find the first empty place Insert the new node in the empty place This will create a Balanced Binary Tree. There are other approaches to insert a new node in a Binary Tree which comes from specific requirements of the problem such as: Set new node as the root and move the previous root node accordingly Place the new node as the left most or the right most leaf node. This is efficiently as we need not traverse the entire tree and can be done in time proportional to the height of the tree. We will follow our approach of inserting the new node at the first empty position. The pseudocode of our insertion operation will be: Node InsertNode(Node root, int data) {
Page
19
// If the tree is empty, create a new node as Root if ( root == NULL ) { root = NewNode( data ); return root ; } // Find the first empty place // where node can be inserted // Queue of Nodes to keep track of nodes to be processed queue < Node > q ; q .push( root ); while ( q is not empty ) { Node temp = q .front(); q .pop(); // If left node is not NULL, put it in queue if ( temp -> left != NULL ) q .push( temp -> left ); // If left node is NULL, empty space have been found else { temp -> left = NewNode( data ); return root ; } // If right node is not NULL, put it in queue if ( temp -> right != NULL ) q .push( temp -> right ); // If right node is NULL, empty space have been found
Page
20
else { temp -> right = NewNode( data ); return root ; } } } Go through the pseudocode and you will get the complete idea. We used a NewNode() function to create a new node with a given value which can be implemented as follows: Node NewNode( int key) { Node newNode = new Node; newNode -> key = key ; newNode -> left = NULL ; newNode -> right = NULL ; return newNode ; Following images clarify the process of inserting a new data in a Binary Tree: Given (Original Tree) :
The above is a preview of the first 20 pages. Register to read the complete e-book.
AI Reading Assistant
Whole-book reading guide from stratified index samples; jump to passages in the text
AI guide
【One-Line Pitch】
A focused, problem-driven tour of binary trees that takes you from traversal fundamentals to interview-style challenges and specialized variants like threaded trees, AVL trees, and treaps. Best suited for developers preparing for coding interviews or contests who want depth beyond a standard data-structures chapter.
【Book Arc】
- **Opening (~0%–12%)**: Establishes the binary tree as a data structure, covering node representation, array-based numbering (children at 2J and 2J+1, parent at floor(J/2)), insertion/deletion, and the core traversal orders. Solves the "what is a tree and how do I walk it" problem.
- **Early (~12%–31%)**: Moves into reconstruction and measurement problems — rebuilding a tree from inorder/preorder traversals (with a hashmap optimization over the naive O(N²) approach), BFS/level-order, diameter via recursion, and subtree matching using traversal-string comparison. Builds the recursive problem-solving reflex.
- **Middle (~38%–54%)**: Tackles classic interview set-pieces: largest independent set, cloning a tree with random pointers, serialization/deserialization (including bitstring encoding), zigzag traversal with two stacks, and converting a tree to a doubly linked list. Here the book emphasizes optimal O(N) approaches and the trade-offs between them.
- **Late (~54% onward)**: Shifts to variants and specializations — skewed trees, threaded binary trees and their operations, binary search trees (sorted-array conversion, k-th smallest, balancing), and self-balancing structures including AVL, Splay, Binary Space Partitioning, Binary Heap, and Treap. This is where the book's claim to unusual depth lives.
- **Ending**: Each chapter closes with a short "Insight" note that reframes the technique as a transferable idea (e.g., extracting a lot from a single traversal, or augmenting a structure to solve a harder problem), aimed at readers who want research-style thinking rather than just answers.
【Key Takeaways】
- **Array indexing unlocks cheap tree operations** (Opening): Numbering a complete tree 1..N gives O(1) parent/child lookup, a foundation reused in heaps and insertion logic.
- **Reconstruction is a traversal-matching game** (Early): Inorder plus preorder uniquely determines a tree; the naive recursive build is O(N²), and a hashmap of inorder indices brings lookup to average O(1).
- **Recursion is the default lens, but watch the cost** (Early): The straightforward diameter solution recomputes subtree heights and lands at O(N²); the book pushes you toward single-pass thinking.
- **One traversal can answer surprisingly hard questions** (Middle): The largest-independent-set solution avoids enumerating subsets, illustrating the "augment and reuse" mindset the Insight notes keep returning to.
- **Serialization needs structure, not just values** (Middle): Marking nulls (e.g., with "#" or a 0/1 bitstring) preserves shape so deserialization can rebuild the exact tree.
- **Multiple valid approaches, ranked by complexity** (Middle): Tree-to-DLL and zigzag traversal are shown in several forms, with the O(N) inorder-with-prev-pointer version flagged as optimal — teaching you to compare, not just accept.
- **BSTs add one ordering rule with big consequences** (Late): The left-less/right-greater property enables k-th smallest, min/max, and sorted-array-to-BST conversions.
- **Balancing variants exist for a reason** (Late): AVL, Splay, Treap, and BSP trees each trade off differently; the book frames them as design choices for real problems like spreadsheet layout and fast graphics rendering.
【Reading Tips】
- **Deep-read the Opening and Early sections** if your traversal and recursion fundamentals are shaky; everything later assumes them.
- **Skim the variant chapters first, then return** — threaded trees and BSP trees are niche for most interviews, but valuable if you face unusual design questions or want research breadth.
- **Treat the Insight notes as the real payoff**: pause after each chapter and ask how the technique generalizes, since that's the book's stated intent.
- **Work the code, don't just read it**: the excerpts show pseudocode and C++ side by side; typing out the O(N) versions (diameter, DLL conversion, serialization) cements the complexity lessons.
- **Watch for complexity claims** — the book repeatedly contrasts O(N²) and O(N) solutions, so keep a running note of which approach wins and why.
【Coverage Limits】
The excerpts sample traversals, reconstruction, serialization, DLL conversion, and variant listings, but do not cover every chapter in full; specific problem counts, later variant details, and the exact structure of the closing chapters are only partially visible. Treat complexity figures and chapter ordering as indicative rather than exhaustive.
Passage locations
Page 8
ary Search Tree 4 0 Different Self Balancing Binary Trees 4 1 AVL Tree 4 2 Splay Tree 4 3 Binary Space Partitioning Tree 4 4 Binary Heap Let us consider that...
View in text
Excerpt 2
y and using the result to compute the diameter recursively. // number as this node is now at the farthest distance if ( d > maxD ) { maxNode = node ; maxD =...
View in text
Excerpt 3
return true*/ return (strstr( preTarget , preSource ) != NULL ); } This method takes time complexity of O(N) and Space complexity of O(N). Note : This proble...
View in text
Excerpt 4
lse { append 1 to s; append n.data to data; encoding(n.left, s, data); encoding(n.right, s, data); } } Following is the implementation in C++ to give you an...
View in text
Recommended for You
{{#thumbnailUrl}}
{{/thumbnailUrl}}
{{^thumbnailUrl}}
{{/thumbnailUrl}}
Loading recommended books...
Failed to load, please try again later
Tip the Site
Scan the WeChat Pay or Alipay code to tip. No login required.
WeChat Pay
Alipay