#include <bits/stdc++.h>
using namespace std;

struct TreeNode{
	int data;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int data):left(nullptr),right(nullptr),data(data){};
};
TreeNode* buildTree(vector<int>&arr){
	if(arr[0]==-1)return nullptr;
	stack<pair<TreeNode*,int>>st;
	
	 TreeNode* root = new TreeNode(arr[0]);st.push({root,0});
	for(int i = 1;i<arr.size();i++){
		auto &top = st.top();
		if(arr[i]==-1){
			if(top.second == 0){
				top.second++;
			}else{
				st.pop();
			}
		}else{
			TreeNode* newNode = new TreeNode(arr[i]);
			if(top.second == 0){
				top.first->left = newNode;
			    top.second++;
			}else{
				 top.first->right = newNode;
			     st.pop();
			
			}
				st.push({newNode,0});
		}
	}
	return root;
	
}
int size(TreeNode* root){
	if(!root)return 0;
return 1+size(root->left)+size(root->right);
	

}
int sum(TreeNode* root){
if(!root)return 0;
int sm = root->data;
return sm+sum(root->left)+sum(root->right);
}
int height(TreeNode* root){
if(!root)return 0;

return 1+max(height(root->left),height(root->right));
}
int maxDepth(TreeNode* root){
if(!root)return 0;
int dpth = 0;
dpth = max(dpth,maxDepth(root->left));
dpth = max(dpth,maxDepth(root->right));
return dpth+1;
}
int maxi(TreeNode* root){
	if(!root)return 0;
	int mx = root->data;
	return max({mx,maxi(root->right),maxi(root->left)});
}
void displayTree(TreeNode* root){
	if(root == nullptr)return;
	if(root)cout<<root->data<<"->";
	if(root->left)cout<<root->left->data<<",";
		if(root->right)cout<<root->right->data<<",";
		cout<<endl;
		displayTree(root->left);
		displayTree(root->right);
}
int main() {
	  vector<int>arr = {10,30,40,-1,-1,60,-1,-1,50,70,-1,-1,-1};
      TreeNode* root = buildTree(arr);
     // displayTree(root);
      cout<<"szie"<<size(root)<<endl;
       cout<<"sum"<<sum(root)<<endl;
        cout<<"height"<<height(root)<<endl;
        cout<<"maxDepth"<<maxDepth(root)<<endl;
          cout<<"maxi"<<maxi(root)<<endl;
	return 0;
}