- Prepare
- Data Structures
- Trees
- Tree : Top View
- Discussions
Tree : Top View
Tree : Top View
+ 0 comments Time Complexity :- O(n) ------ HashMap
void topView(Node * root) { map<int,int>i; queue<pair<Node*,int>>q;q.push({root,500}); while(!q.empty()){ pair<Node*,int> t=q.front();q.pop(); if(t.first->left)q.push({t.first->left,t.second-1}); if(t.first->right)q.push({t.first->right,t.second+1}); if(!i[t.second])i[t.second]=t.first->data; } for(auto k:i)cout<<k.second<<" "; }
+ 0 comments bloc_lst = [] def blocked_list(root): if root is None: return if root.left: if root.left.right: #print(root.left.right.info,end=" ") bloc_lst.append(root.left.right.info) if root.right: if root.right.left: #print(root.right.left.info,end=" ") bloc_lst.append(root.right.left.info) blocked_list(root.left) blocked_list(root.right) from collections import defaultdict def topView(root): if not root: return blocked_list(root) blocked_nodes = bloc_lst # Create a dictionary to store nodes at each horizontal distance from the root hd_map = defaultdict(list) # Create a queue for level-order traversal queue = [(root, 0)] # Each element is a tuple (node, horizontal distance) while queue: node, hd = queue.pop(0) # Check if the node is not blocked if node.info not in blocked_nodes: hd_map[hd].append(node.info) if node.left: queue.append((node.left, hd - 1)) if node.right: queue.append((node.right, hd + 1)) # Print the top view nodes in order of horizontal distance for hd in sorted(hd_map): print(hd_map[hd][0], end=" ")
+ 1 comment is this right?
include
include
include
using namespace std;
struct Node { int data; Node* left; Node* right; };
void topView(Node* root) { if (root == nullptr) { return; }
// Create a map to store the horizontal distance and the corresponding node data map<int, int> verticalMap; // Create a queue for level-order traversal queue<pair<Node*, int>> levelOrder; // Initialize the queue with the root and horizontal distance 0 levelOrder.push({root, 0}); while (!levelOrder.empty()) { Node* current = levelOrder.front().first; int horizontalDistance = levelOrder.front().second; levelOrder.pop(); // If this horizontal distance is not in the map, add it to the map if (verticalMap.find(horizontalDistance) == verticalMap.end()) { verticalMap[horizontalDistance] = current->data; } // Enqueue the left and right children with updated horizontal distances if (current->left != nullptr) { levelOrder.push({current->left, horizontalDistance - 1}); } if (current->right != nullptr) { levelOrder.push({current->right, horizontalDistance + 1}); } } // Print the top view from left to right for (const auto& entry : verticalMap) { cout << entry.second << ' '; }
}
int main() { // Create a sample binary tree and call topView Node* root = new Node{1, new Node{2, nullptr, nullptr}, new Node{3, nullptr, nullptr}}; cout << "Top View of Binary Tree: "; topView(root);
In this version of the code, I've used a map to store the nodes seen at each horizontal distance, ensuring that only the topmost node at each distance is recorded. This simplifies the code and ensures that it works correctly for various binary tree structures. cout << endl;
return 0;
}
+ 0 comments runs in O(n) time, not O(nlog n), no need to search for horizontal level in a map, the checking is done in constant time with the leftside and rightside vectors
void topView(Node * root) { queue<pair<Node*, int>> levelOrder; vector<int> leftside = {root->data}; vector<int> rightside; levelOrder.push({root, 0}); while (!levelOrder.empty()) { Node* temp = levelOrder.front().first; int currentHorizontal = levelOrder.front().second; if (currentHorizontal <=0 and abs(currentHorizontal) == leftside.size()) { leftside.push_back(temp->data); } else if (currentHorizontal > 0 and currentHorizontal == rightside.size()+1) { rightside.push_back(temp->data); } if (temp->left != NULL) { levelOrder.push({temp->left, currentHorizontal-1}); } if (temp->right != NULL) { levelOrder.push({temp->right, currentHorizontal+1}); } levelOrder.pop(); } for (int i=leftside.size()-1; i >= 0; i--) { cout << leftside[i] << ' '; } for (int i=0; i < rightside.size(); i++) { cout << rightside[i] << ' '; } }
+ 0 comments python 3 def topView(root): queue=[] top_view={} queue.append([root,0]) while(queue): node,level=queue.pop(0) # to remove front element if level not in top_view: top_view[level]=node.info if node.left: node.left.level=level-1 queue.append((node.left, level - 1)) if node.right: node.right.level=level+1 queue.append((node.right, level + 1)) print(top_view) for level in sorted(top_view): print(top_view[level],end=" ")
Sort 910 Discussions, By:
Please Login in order to post a comment